F - Grid of Lamps
We have a grid of lamps. Some of the
lamps are on, while others are off. The luminosity of a row/column is the
number of its lighted lamps. You are given a permutation of the luminosities of
the rows and a permutation of the columns'. Unfortunately, these values are not
accurate but we know at least that they are not overestimates. You should tell
us the minimum possible number of lighted lamps in this grid.
As an example, consider the following
grid. The lighted lamps are shown by 1's and unlighted ones by 0's.
|
1 |
0 |
1 |
1 |
0 |
|
1 |
1 |
1 |
1 |
1 |
|
0 |
0 |
0 |
1 |
1 |
|
0 |
1 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
0 |
The actual
luminosities of the rows are <3,5,2,3,1>. A permutation of them could be
<1,2,5,3,3>, and the inexact values you'd be given could be
<1,1,4,2,3>.
Input
The first line of input contains an
integer T≤100 denoting the number of test-cases. Each test-case begins with two
integers M and N, both in the interval [1, 1000], determining the number of
rows and columns of the grid respectively. The next two lines give the
luminosities, the first for rows (M values) and the second for columns (N
values).
Output
For each test-case, on a single line,
output the minimum conceivable number of lighted lamps.
|
Sample
Input |
Sample
Output |
|
3 2 2 2 0 0 2 1 4 2 1 0 1 1 2 4 3 1 0 2 1 2 |
3 3 5 |