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 ith 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 ith type back in their place. Help him in finding the minimum number of moves it will take to re-order these coins.
Input Format:
Output Format: For each test case, print an integer that denotes the minimum number of moves Alex will take to re-order coins.
Constraints:
1≤T≤101≤N≤1051≤A[i]≤1091≤K[i]≤109
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.