Matrix sum

Time Limit: 20000/10000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)

Problem Description

sweet和zero在玩矩阵游戏,sweet画了一个N * M的矩阵,矩阵的每个格子有一个整数。zero给出N个数Ki,和M个数Kj,zero要求sweet选出一些数,满足从第 i 行至少选出了Ki个数,第j列至少选出了Kj个数。 这些数之和就是sweet要付给zero的糖果数。sweet想知道他至少要给zero多少个糖果,您能帮他做出一个最优策略吗?

Input

首行一个数T(T <= 40),代表数据总数,接下来有T组数据。

每组数据:

第一行两个数N,M(1 <= N,M <= 50)

接下来N行,每行M个数(范围是0-10000的整数)

接下来一行有N个数Ki,表示第i行至少选Ki个元素(0 <= Ki <= M)

最后一行有M个数Kj,表示第j列至少选Kj个元素(0 <= Kj <= N)

Output

每组数据输出一行,sweet要付给zero的糖果数最少是多少

Sample Input

1
4 4
1 1 1 1
1 10 10 10
1 10 10 10
1 10 10 10
1 1 1 1
1 1 1 1

Sample Output

6

Source

sweetzero

Manager

Information
Solved Number168
Submit Number396
Problem Tags
flows
graphs
No tag edit access
温馨提示:AC后可以编辑标签哦. ^-^
Login
LoginCancel