Alex loves to collect coins. He has been doing so since his childhood. He has a total of \(N\) different types of coins, numbered from \(0\) to \(N-1\). The \(i^{th}\) type has \(A[i]\) coins. Since, Alex is free right now, he wishes to keep these coins in order but in a specific way.
Initially no coins are in their place.
In one move, he can keep at most \(K[i]\) coins of the \(i^{th}\) type back in their place. Help him in finding the minimum number of moves it will take to re-order these coins.
Input Format:
- The first line of input contains a single integer \(T\), which denotes the number of test cases.
- The first line of each test case contains an integer \(N\), denoting the number of types of coins.
- The second line of each test case contains \(N\) space-separated integers, where the \(i^{th}\) integer denotes the value of \(A[i]\).
- The third line of each test case contains \(N\) space-separated integers, where the \(i^{th}\) integer denotes the value of \(K[i]\).
Output Format: For each test case, print an integer that denotes the minimum number of moves Alex will take to re-order coins.
Constraints:
For test case 1:
In the first move, he keeps 3 coins of type 0, 1 coin of type 1, 3 of type 2, and 1 of type 3. So the remaining coins are {2, 0, 6, 1}.
In the second move, he keeps 2 coins of type 0, 3 of type 2, and 1 of type 3. So the remaining coins are {0, 0, 3, 0}.
In the third move, he keeps 3 coins of type 2. Now there are no remaining coins.
Hence, it takes him 3 moves to re-order.
For test case 2:
In the first move, he keeps 1 coin of type 0. Now there are no remaining coins.
Hence, it takes him 1 move to re-order.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor