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?

The first line of the input contains three integer numbers N, K and P (1≤ N≤ 600; 1≤ KN; 1≤ P≤ 106). 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≤ CiK for all i = 1, 2,..., N).

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.

sample input
sample output
4 2 10
1 2
1 2
5 2
3 1
3 2
4 3 1

Online Contester Team © 2002 - 2010. All rights reserved.