| [Home|Training|Problems|Contests|C Language] | [Login|Register] |
|
Problems Status Rank |
Problem 1238
Boys and Girls
Time Limit: 1000ms
Memory Limit: 65536kb Description
The annual Children’s Day is coming. Teacher Chen with other teachers is considering rewarding the acmer of USTC. Then what is the present? Surely, it would be the lolipop! Assuming there are N boys, M girls. The ith boy will get Ai candies, the ith girl will get Bi candies if there is no restriction. But there keeps intimate relationship between some boys and some girls (You know it!), so persons in pair won’t get candies simultaneously( Assuming no gay and lesbian and more complex relationship here). The following example will explain it:Assuming there is a boy B and a girl G, if no restriction, Boy B will get x candies, Girl G will get y candies. But based on the intimate relationship between them , they can’t get candies simultaneously, so the most candies they get are Max(x,y). Here comes the problem: choose a group which consists of some girls and boys to get the most candies. What’s more, the solution must guarantee that no so-called intimate relationship exists in the group. You, as a talented programmer, must have the ability to find the amount of candies the group can get. Right? Input
The first line of input contains a number T, representing the numbers of test cases .Then each test case contains three parts:The first part: N and M(1<=N,M<=200),representing the numbers of boys and girls respectively. The second part: N numbers, indicating the candy numbers, Ai(0<Ai<=100) for the ith boy under non-restraint condition from left to right(1<=i<=N). The third part: M numbers, indicating the candy numbers, Bi (0<Bi<=100) for the ith girl under non-restraint condition from left to right(1<=i<=M). The last part: one 0-1 matrix with its size N by M. Considering the ith row, the jth column element of it. 1 represents that the ith boy and the jth girl keep intimate relationship, so they can’t get candies simultaneously. Otherwise 0,representing they can get candies simultaneously. Output
Output the amount of candy the group u choose can get.
Sample Input
1 2 2 3 4 3 5 0 1 0 0 Sample Output
12 |