TCCC '24 June P5 - Transfer Window

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.2s
Memory limit: 512M

Author:
Problem type

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


Comments

There are no comments at the moment.