Thornhill Computer Club 2024 - June Contest - Problem 5

After winning the TCC (The Champions Cup), Real Chamartin is looking to buy new players. However, due to MF (Monetary Fairness), the club can only purchase a player once their earnings are at least equivalent to the price.

The club's earnings are represented by a list of ~N~ ~(N \le 1000)~ integers, where ~a_i~ ~(0 \le a_i)~ represents the earnings on day ~i~ ~(1 \le i \le N)~. Information about the ~M~ ~(M \le 1000)~ players, i.e. the cost of player ~j~, ~A_j~, and the day the club plans to purchase them, ~B_j~, have also been provided.

Input Specification

The first line of input contains two integers ~N~ and ~M~, separated by spaces. The second line of input contains ~N~ space-separated integers. The last ~M~ lines of input will each contain ~A_j~ and ~B_j~, separated by spaces.

Output Specification

Print the maximum number of days the club would have to delay the signing of a player, i.e. the day the player is first available minus the proposed day. If the player is already available on the proposed day, the delay is zero.

Scoring

• Inputs 1-2: ~(N, M \le 10).~
• Inputs 2-10: No further constraints.

Sample Input 1

3 2
4 4 2
9 2
3 3

Sample Output 1

1

Explanation of Sample Output 1

The club delays the signing of player 1 by one day.

Clarification

For each player, imagine you are only buying that specific player, and not the others, when finding the delay (if I wanted to buy that player, how long would the delay be).