P7344 [DSOI 2021] Building Blocks.

"Have you heard of the death game? It is where you are locked in a pitch-dark room, given some hard-to-understand clues, and if you cannot solve the problem, you are given the gift of death. “Huh? Why panic? Right now you are only in this airtight room. What I want you to answer is only a simple question. “Any objections? Fine, let the game begin.”

“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.)

**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.

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$.

**[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. | Subtask | Score | $n,m,a_i,b_i \le$ | Special Property | | :-----: | :---: | :---------------: | :-----------------------------------: | | 1 | 7pts | $3$ | None | | 2 | 8pts | $10$ | The number of $-1$ in array $a$ is at most $4$ | | 3 | 8pts | $1000$ | Guarantee $a_i \ne -1$ | | 4 | 12pts | $2\times10^4$ | Guarantee $a_i \ne -1$ | | 5 | 7pts | $1000$ | Guarantee all $b_i$ are equal | | 6 | 8pts | $2\times10^4$ | Guarantee all $b_i$ are equal | | 7 | 15pts | $1000$ | None | | 8 | 35pts | $2\times10^4$ | None | 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