Ninja and Candies Problem

Ninja, a boy from Ninjaland, receives 1 coin every morning from his mother. He wants to purchase exactly 'N' candies. Each candy usually costs 2 coins, but it is available for 1 coin if on sale. Ninja aims to acquire exactly K[i] candies of the i-th type by purchasing them in the evening.

Ninja can buy any number of candies, including zero, of any type on any day, provided he has sufficient money. If candies are on sale, he can buy them at the discounted price of 1 coin; otherwise, the regular price is 2 coins.

In the candy shop, there are 'M' special sale offers. The j-th offer (D[j], C[j]) indicates that candies of the C[j]-th type are on sale on the D[j]-th day.

Ninja's goal is to purchase all candies as quickly as possible. Your task is to calculate the earliest day on which Ninja can buy all the candies.

Input:

The first line of input contains an integer ‘T’, which represents the number of test cases. Then, the test cases follow. Each test case begins with a line containing two space-separated integers, ‘N’ and ‘M’, which denote the total number of candy types and the number of special offers, respectively. The following line in each test case contains ‘N’ space-separated integers K[i], indicating the number of candies of each type that Ninja wants to buy. The next M lines contain two space-separated integers (D[i], C[i]), denoting that candies of the C[i]-th type are on sale on the D[i]-th day.

Output:

For each test case, print the minimum day by which Ninja can purchase all candies. Each result should appear on a new line.

Example:

Consider the following test case:

Input:
T = 1
N = 3, M = 3
K = [2, 3, 5]
Special Offers = [(1, 2), (3, 1), (5, 3)]

Output:
9

Constraints:

• 1 <= T <= 10
• 1 <= N, M <= 10^4
• 0 <= K[i] <= 10^4
• 1 <= C[i] <= N
• 1 <= D[i] <= 10^4
• The sum of all K[i] within a test case is less than 5000.

Note:

You don’t need to print anything explicitly; the task involves implementing the function to compute the answer.