Duck Contest

Laser Attack

Program time limit: 1 second

Program memory limit: 512 MB

Duck tito's duck empire has experienced the attacks of the incoming earthworms!!!

There are N incoming earthworms, each with a length of $A_i$, you can imagine them to be an array. Luckily, Duck tito has a valiant army of M duck solders, each of them has an eating power $E_i$, and eating time, $T_i$.

Being proud ducks, Duck tito can only send one duck soldier at a time to face the earthworm army. This duck soldier can apply its eating power, $E_i$ on any continuous range of the array of earth worms they like at once, however, dealing this eating power will cost the whole army $T_i$ worth of time, putting the empire into greater risk.

Each earthworm that got attacked with the eating power will have its length, $A_i$ decreased by $E_i$. If $A_i \leq 0$, the earthworm is dead and removed from the array.

Help Duck tito determine the shortest time required to eliminate the incoming earthworms!

Input

  • The first line of inputs contains two integers, N and M.
  • The following line contains N integers, with the ith integer being $A_i$.
  • The following M line contains $2$ integers in each line, $E_i$ and $T_i$.

You should read from standard input.

In Python, you could use the following code.

N, M = map(int, input().split())
A = list(map(int, input().split()))
E = []
T = []
for _ in range(M):
    cost, power = map(int, input().split())
    E.append(cost)
    T.append(power)

In C or C++, you could use the following code.

scanf("%d %d", &N, &M);  
for(int i = 0; i < N; i++) scanf("%d", &A[i]);
for(int i = 0; i < M; i++) scanf("%d %d", &E[i], &T[i]);

Constraints

For all test cases:

  • $0 \le N \le 10^7$.
  • $1 \le M, A_i, E_i, T_i \le 1000$.

Additionally:

  • For Subtask $1$ ($20\%$ of points): $M = 1$.
  • For Subtask $2$ ($30\%$ of points): $N \leq 1000$.
  • For Subtask $3$ ($50\%$ of points): there are no additional constraints.

Output

one integer, the shortest time required.

You should write to standard output.

In Python, you could use the line print(answer).

In C or C++, you could use the line printf("%d\n", answer);.

Sample Input 1

5 2
3 3 3 5 5
5 3
3 2

Sample Output 1

3

Explanation 1

In this case, if Duck Tito sending out the first duck once, it will eat all the earthworms if it chooses the range $[1,5]$. The total time will be $3$.

Sample Input 2

3 2
10 2 2
2 3
8 5

Sample Output 2

8

Explanation 2

Duck Tito can send the first soldier with the eating power of $2$ to all the earth worms, and then send the second worm with the eating power of $8$ to eat the only remaining earthworm.

Scoring

For all subtasks (worth $20\%$, $30\%$, and $50\%$ of points, as per the Constraints section), your program will be run on multiple secret test cases one after another, and if it produces the correct output for all test cases, it solves that subtask. Your program will receive the points for each subtask it solves. Recall that your final score on the task is the score of your highest scoring submission.

Submit

The contest ended at 8:16 p.m. AEST on Thursday 2nd July. All submissions will be unofficial .