304. Mars Stomatology
Time limit per test: 0.5 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard
Martian girl Kate has a toothache. The martian anatomy is very specific. They all have
N teeth, each situated on one of
K gums. Kate should pay dentist
Ai mars euros for the treatment of
i-th tooth. Moreover, Kate should pay
Bj euros for the anesthesia of the gum
j if this gum has at least one tooth cured. What is the maximal number of teeth Kate can cure if parents gave her
P mars euros?
Input
The first line of the input contains three integer numbers
N,
K and
P (1≤
N≤ 600; 1≤
K≤
N; 1≤
P≤ 10
6). The second line contains the sequence of
K integer numbers
B1,
B2,...,
BK, where
Bj is the cost of anesthesia of the
j-th gum (1≤
Bj≤ 600 for all
j = 1, 2,...,
K). Each of the following
N lines contains the description of tooth. Each description is the pair of integer numbers
Ai and
Ci, where
Ai is the cost of curing of the
i-th tooth,
Ci is the number of the gum the tooth occupies (1≤
Ai≤ 600; 1≤
Ci≤
K for all
i = 1, 2,...,
N).
Output
Write to the first line of the output the maximal number of cured teeth
S. Write to the second line
S numbers of the cured teeth from the given set. If there are several solutions output any of them.
Example(s)
sample input | sample output |
4 2 10
1 2
1 2
5 2
3 1
3 2
|
3
4 3 1
|