Description

“Now, what you have are some unit cubes with side length $1$. And I, the owner of the game, will tell you the front view and the left view of the final 3D shape you build. You think I want you to build exactly that shape? Don’t panic, the game is far from that simple. In the front view, I will hide some columns, so you cannot observe their heights.

“To make the game more interesting, I rule that the heights of those columns you cannot observe are arbitrary—this can be decided by you.

“I suppose, my dear player, you have known since primary school that a shape cannot be uniquely determined with only the front view and the left view, not to mention that part of the front view is hidden by me. Therefore, let $k$ be the number of blocks that can be used to build a shape consistent with what I give. Please tell me: at most, how many integers $k$ can satisfy my requirements?” (That is, you should first decide the values of the unknown columns yourself, and then compute $k$ based on that choice. You need to choose the heights so that the number of possible values of $k$ is maximized.)

Input Format

This problem contains multiple test cases.
The first line contains an integer $T$, the number of test cases.
For each test case:
The first line contains two integers $n,m$, representing the length and width of the final block shape.
The second line contains $n$ integers. The $i$-th integer $a_i$ is the height of blocks seen in the $i$-th column from left to right in the front view. In particular, if $a_i=-1$, then the height of this column is arbitrary.
The third line contains $m$ integers. The $i$-th integer $b_i$ is the height of blocks seen in the $i$-th column from back to front in the left view. It is guaranteed that there is no column with unknown height.

Output Format

For each test case, output one integer per line, representing the maximum number of integers $k$ that can satisfy the requirements. In particular, if there is no integer $k$ that satisfies the conditions, output $0$.

2
3 2
1 2 1
2 2
2 2
-1 2
2 2

3
5

Hint

[Sample Explanation]
For the first test case:
The feasible values of $k$ are $6,7,8$.
For each value of $k$, one possible construction is as follows (the top view is shown; the numbers indicate the height of that cell):

For the second test case:
When the heights of the unknown columns are set to $2$, the number of valid $k$ values is maximized. There are $5$ such values: $4,5,6,7,8$.

[Constraints and Limits]
This problem uses bundled testdata. You must pass all test points in a Subtask to obtain the score for that Subtask.

For $100\%$ of the testdata, $1 \le n,m \le 2\times10^4$, $-1 \le a_i \le 2\times10^4$, $0 \le b_i \le 2\times10^4$, and $0 \le T \le 100$.

The input size of this problem is large. Please use a fast input method.

Translated by ChatGPT 5