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 i-th 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?

The first line of the input contains three integer numbers N, K and P (1≤ N≤ 600; 1≤ K≤ N; 1≤ P≤ 10⁶). The second line contains the sequence of K integer numbers B₁, B₂,..., B_K, where B_j is the cost of anesthesia of the j-th 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 i-th 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).

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	3 4 3 1