{"problem":{"name":"F. Friendly Game","description":{"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.   In this game, you are given a matrix of $N$ rows and $M$ columns","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10256F"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10256F","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}