提示: 欢迎访问OurACM平台。
Problem 1689 World of warcraft

Accept: 56    Submit: 149
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description


The world of warcraft is one of the most popular games among young adults. Maybe you are also interested in it.To simplify this problem ,here we have a different rule:
There are n monsters,each has an energy value and belongs to a race.In order to kill a monster from race A,you must first spend some energy tolearn the special skill to fight with race A,then spend the same energy asthe monster has to kill it. And after that , when you want to kill anothermonster which is also from race A,you needn't to learn the special skill again,because you have already grasp it. Now your energy is P,what is the maximum number of monsters you can kill.

Input

The first line will contain three numbers n,m and p (1<=m<=n<=600,1<=p<=1000000)indicates there are n monsters,m races, and your energy is p.
The second line will contain m numbers,the ith number is Si(1<=Si<=600),it represents the energy you have to spend for learning special skill to fight with the ith race.
The next n lines,each has two numbers Ei(1<=Ei<=600) and Ri(1<=Ri<=m) ,describing a monster,the energy it has and the race it belongs to .

Output

one line containing the maximum number of monsters you can kill.

Sample Input

3 2 11 3 1 3 2 2 1 2 1 3 2 8 3 2 3 2 2 1 3 1

Sample Output

3 2

Source

FOJ月赛-2009年3月--- LWX

Submit  Back  Status  Discuss