New update is available. Click here to update.

Binary Search Notes

Binary Search on Matrix

0% completed

Search in Rotated Sorted Array

Search in a 2-D Matrix

Search in a 2-D Matrix II

First and Last Position of an element in sorted array

Occurrence of x in a sorted array

Binary Search on Answer

0% completed

Allocate Books

Recycling Pens

Square root of an Integer

Aggressive Cows

Painter's Partition Problem

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

Problem

Submissions

Solution

New

Discuss

Ninja And Candies

Last Updated: 23 Feb, 2023

Medium

0/80

Avg time to solve 15 mins

Success Rate 85 %

19 upvotes

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.

Detailed explanation ( Input/output format, Notes, Images )

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 :

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 :

Sample Output 2:

Auto

Console