Problem

Submissions

Solution

New

Discuss

5

Difficulty: MEDIUM

Avg. time to solve

15 min

Success Rate

85%

Problem Statement

Suggest Edit

```
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.
```

```
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.
```

```
You do not need to print anything; it has already been taken care of. Just implement the given function.
```

```
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.
```

```
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
```

```
4
5
```

```
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.
```

```
1
5 6
1 2 0 2 0
2 4
3 3
1 5
1 2
1 5
2 3
```

```
8
```

Console