Candy

There are N candies and M kids, the teacher will give this N candies to the M kids. The i-th kids for the j-th candy has a preference for like[i][j], if he like the sugar, like[i][j] = 1, otherwise like[i][j] = 0. If the i-th kids get the candy which he like he will get K glad value. If he or she do not like it. He will get only one glad value. We know that the i-th kids will feel happy if he the sum of glad values is equal or greater than B[i]. Can you tell me whether reasonable allocate this N candies, make every kid feel happy.

The Input consists of several cases .The first line contains a single integer t .the number of test cases.
For each case starts with a line containing three integers N, M, K (1<=N<=13, 1<=M<=13, 2<=K<=10)
The next line contains M numbers which is B[i](0<=B[i]<=1000). Separated by a single space.
Then there are M*N like[i][j] , if the i-th kids like the j-th sugar like[i][j]=1 ,or like[i][j]=0.

If there have a reasonable allocate make every kid feel happy, output "YES", or "NO".

2
3 2 2
2 2
0 0 0
0 0 1

3 2 2
2 2
0 0 0
0 0 0

Case #1: YES
Case #2: NO

Give the first and second candy to the first kid.
Give the third candy to the second kid.
This allocate make all kids happy.

BJTU

2012 Multi-University Training Contest 3