Mixed Problems related to Binary Search
0% completed
Chess Tournament
Ninja and Candies
Minimum time to Solve the Problems
Square Submatrix with Sum less than or equal to K
Smart Intervals
Distribute N candies among K people
Search in Infinite Sorted array of 0 and 1
Find pair Sum in rotated sorted Array
Find peak element
Find Missing Number in AP
Find Best Insertion Position in Array
5

Ninja And Candies

Difficulty: MEDIUM
Avg. time to solve
15 min
Success Rate
85%

Problem Statement
Suggest Edit

Ninja is a boy who lives in ninjaland. Every day, during the morning he gets 1 coin from his mother. He wants to buy exactly ‘N’ candies. Each of the candies cost 2 coins usually and 1 coin if it is on sale. Ninja has to buy exactly K[i] candies of the i-th type(he buys candies in the evening).

Ninjas can buy any(possibly zero) number of candies of any type during any day(if he has enough money to do it). If the candy is on sale he can buy it for 1 coin and otherwise he has to buy it for 2 coins.

There are ‘M’ special offers in the candy shop. The j-th offer (D[j], C[j]) means that candies of the C[j]-th type are on sale during the D[j]-th day.

Ninja wants to buy all candies as soon as possible. Your task is to calculate the minimum day when he can buy all the candies.

Input Format
The first line of input contains an integer ‘T’ denoting the number of test cases to run. Then the test cases follow.

The first line of each test case contains two space separated integers ‘N’ and ‘M’ denoting the total number of types of candies and the number of special offers in the candy shop.

The second line of each test case contains ‘N’ space-separated integers K[i], denoting the number of candies of each type Ninja has to order.

The next M-lines contain two space-separated integers (D[i], C[i]), denoting that the candy of C[i] type is on sale on the D[i]-th day.
Output Format :
For each query, print the minimum day when the Ninja can order all candies.

Output for each test case will be printed in a new line. 
Note:
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 10
1 <= N, M <= 10^4
0 <= K[i] <= 10^4
1 <= C[i] <= N
1 <= D[i] <= 10^4

Here N denotes the total number of candies and M denotes the total number of special offers.
Here K[i] denotes the number of candies of the i-th type Ninjas has to order.
Here C[i]  and D[i] denote that the candy if the C[i]-th type will be on sale on the D[i]-th day.
Sum of K[i]’s in each test case will be less than 5000.
Sample Input 1 :
2
4 4
1 0 2 0
1 1
1 3
2 1
2 3
3 3
1 1 1
1 1
1 2
1 3
Sample Output 1:
4
5
Explanation of Input 1:
For test case 1, Ninja can buy candies in the following manner-

• Buy candy of type 1 on day 1 for 1 coin.
• Buy candy of type 3 on day 2 for 1 coin.
• Buy candy of type 3 on day 4 for 2 coins.

For test case 2, Ninja can buy candies in the following manner-
• Buy candy of type 1 on day 1 for 1 coin.
• Buy candy of type 2 on day 3 for 2 coins.
• Buy candy of type 3 on day 5 for 2 coins.
Sample Input 2 :
1
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3
Sample Output 2:
8
Reset Code
Full screen
copy-code
Console