New update is available. Click here to update.

Kevin and the tower of coins

Posted: 7 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

Kevin has ‘N’ coins. Each coin has a specific width and diameter. Kevin wants to build a tower using these coins such that each coin in the tower has strictly less width and diameter as compared to all coins placed below this coin.

You have to find the maximum height of the tower that Kevin can build by using these coins.

Note:

The height of the tower is calculated by adding the width of all the coins used in the formation of this tower.
Input Format:
The first line contains a single integer ‘T’ representing the number of test cases. 

The first line of each test case will contain a single integer ‘N’ which denotes the number of coins available.

The next ‘N’ lines contain the two space-separated integers “ARR[i][0]” and “ARR[i][1]”, where “ARR[i][0]” is the width of the ‘i-th’ coin and “ARR[i][1]” is the diameter of the ‘i-th’ coin.
Output Format:
For each test case, return the maximum possible height of the tower.

Output for every test case will be printed in a separate line.
Note:
You don’t need to print anything; It has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 50
1 <= N <= 10^4
1 <= ARR[i][0] and ARR[i][1] <= 10^5

Time limit: 1 sec