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≤ K≤ N; 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≤ Ci≤ K 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.
4 2 10
4 3 1
Codeforces (c) Copyright 2010-2021 Mike Mirzayanov