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
A_{i} mars euros for the treatment of
ith tooth. Moreover, Kate should pay
B_{j} 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
B_{1},
B_{2},...,
B_{K}, where
B_{j} is the cost of anesthesia of the
jth gum (1≤
B_{j}≤ 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
A_{i} and
C_{i}, where
A_{i} is the cost of curing of the
ith tooth,
C_{i} is the number of the gum the tooth occupies (1≤
A_{i}≤ 600; 1≤
C_{i}≤
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
