Problem D. Dissatisfied by spice

Author:A. Baranov   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

Vasya became the chef of an elite restaurant. His clients are many and has very particular taste preferences. One of the most important features of restaurant dishes are various spices.

Each client requires specific amount of every kind of spice, according to his taste. If his dish does not contain enough of some spice, client becomes dissatisfied.

Since there is only a limited amount of each kind of spice in the kitchen, sometimes it is impossible to satisfy all clients. Your program must help Vasya to minimize number of dissatisfied clients.

Input file format

Input file contains integer number of kinds of spices M, followed by M integers Aj — amount of available spice of each kind.

Following is integer N — number of clients, and matrix Pi j — amount of spice of j-th kind required by i-th client. The order is: all spices for the first client, then all spices for the second client, etc.

Output file format

Output file must contain indexes of clients who will remain satisfied. Clients are indexed from zero.

Constraints

0 < M ≤ 5, 0 < N ≤ 50, 0 ≤ (Aj, Pi j) < 10

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
5
6 4 5 7 2

4
1 2 3 4 1
3 3 1 5 1
2 1 2 1 0
0 1 0 1 0
3
2
0
2
5
6 4 5 7 2

4
1 2 3 4 3
7 3 1 0 1
2 1 6 1 2
0 5 0 1 0
 

0.072s 0.011s 13