[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 i^{th} boy will get A_{i} candies, the i^{th} girl will get B_{i} 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 i ^{th} 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 i ^{th} 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 i ^{th} row, the j^{th} column element of it. 1 represents that the i^{th} boy and the j^{th} 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 |

University of Science and Technology of China

Online Judge for ACM/ICPC

Processed in 1.3ms with 1 query(s).

Online Judge for ACM/ICPC

Processed in 1.3ms with 1 query(s).