{"raw_statement":[{"iden":"statement","content":"Ghita and Lica decided to play $T$ friendly games. Since he is competitive, your task is to help Ghita win every single one of them. \n\n In this game, you are given a matrix of $N$ rows and $M$ columns. You earn a point by placing a marble in any cell of said matrix. However, there is a rule that Lica has imposed on Ghita and which you must follow - on each row and column, you are only allowed to place a certain amount of marbles at most. \n\n In order for Ghita to win, you must place the marbles in such a way that all the requirements are fulfilled while maximising the total number of points.  \n\nThe first line has an integer T ($1 <= T <= 10^5$) - the number of games.\n\nOn the first line of a test's input, there are two integers, namely: $N$, the number of rows and $M$, the number of columns.\n\nThe second line of input contains N values $a_i$ ($1 <= i <= N$, $0 <= a_i <= M)$ - the maximum number of marbles that can be placed on row $i$.\n\nThe third line of input contains M positive integers $b_j$ ($1 <= j <= M$, $0 <= b_j <= N$) - the maximum number of marbles that can be placed on column $j$.\n\nPlease note that the sum of $N$, respectively the sum of $M$ will not exceed $10^6$ over all test cases.\n\nFor each test, you ought to print, on a line, a value $x$ which represents the maximum number of points that can be obtained while satisfying Lica's conditions.\n\n"},{"iden":"input","content":"The first line has an integer T ($1 <= T <= 10^5$) - the number of games.On the first line of a test's input, there are two integers, namely: $N$, the number of rows and $M$, the number of columns.The second line of input contains N values $a_i$ ($1 <= i <= N$, $0 <= a_i <= M)$ - the maximum number of marbles that can be placed on row $i$.The third line of input contains M positive integers $b_j$ ($1 <= j <= M$, $0 <= b_j <= N$) - the maximum number of marbles that can be placed on column $j$.Please note that the sum of $N$, respectively the sum of $M$ will not exceed $10^6$ over all test cases."},{"iden":"output","content":"For each test, you ought to print, on a line, a value $x$ which represents the maximum number of points that can be obtained while satisfying Lica's conditions."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of windows, indexed $ 1 $ to $ n $.  \nLet $ t \\in \\{1, \\dots, n\\} $ be the unknown initial position of the target.  \nAfter each miss at window $ w $, the target moves right by 1 if $ t < n $; if $ t = n $, it stays.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 1000 $  \n2. Target starts at some $ t \\in \\{1, \\dots, n\\} $, unknown.  \n3. After a miss at window $ w $, if $ t < n $, then $ t \\leftarrow t + 1 $.  \n4. Shooting at window $ w $ when $ t = w $ results in immediate win.  \n\n**Objective**  \nFind a sequence $ (a_1, a_2, \\dots, a_k) $ with minimal $ k $ such that, for any initial $ t \\in \\{1, \\dots, n\\} $, there exists $ i \\in \\{1, \\dots, k\\} $ with $ a_i = t + i - 1 $, and $ t + i - 1 \\leq n $.  \n\n**Solution**  \nThe minimal number of shots is $ k = n $.  \nThe optimal shooting sequence is:  \n$$\na_i = i \\quad \\text{for } i = 1, 2, \\dots, n\n$$","simple_statement":"Shoot windows in order from right to left: n, n-1, ..., 1.  \nThis guarantees hitting the target in at most n shots.  \nMinimal number of shots is n.  \nSequence: n, n-1, ..., 1.","has_page_source":false}