You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Coin Toss Earnings

Problem Statement

Bessie is planning to toss a coin $N$ $(1 \leq M \leq N \leq 5000)$ times. She also has a counter, which starts at $0$. The outcome of each toss will impact the counter and Bessie's earnings in the following ways:

• If the coin lands on heads: Bessie increases the counter by 1 and receives $X_i$ $(1 \leq X_i \leq 10^9)$ dollars.
• If the coin lands on tails: she resets the counter to $0$ and doesn't receive any money.

Additionally, there are $M$ $(M \leq N)$ types of streak bonuses. For each type $i$, Bessie earns a bonus of $Y_i$ $(1 \leq Y_i \leq 10^9)$ dollars each time the counter shows $C_i$.

Bessie is interested in finding out the maximum amount of money she can potentially earn from this coin-tossing game.

INPUT FORMAT (input arrives from the terminal / stdin):

The input is provided in the following format:

• The first line contains two integers $N$ and $M$.
• The second line contains $N$ integers, $X_i$ $(1 \leq A_i \leq N)$ for $1 \leq i \leq N$, separated by spaces.
• The next $M$ lines each contain two integers $C_i$ and $Y_i$.

OUTPUT FORMAT (print output to the terminal / stdout):

Print a single integer: the maximum amount of money that Bessie can earn from the coin-tossing game.

SAMPLE INPUT 1:

6 3
2 7 1 8 2 8
2 10
3 1
5 5

SAMPLE OUTPUT 1:

48

If Bessie gets heads, heads, tails, heads, heads, heads, in this order, the following amounts of money are awarded:

• In the 1st coin toss, the coin lands on heads. The counter's value changes from $0$ to $1$ and Bessie receives $2$ dollars.
• In the 2nd coin toss, the coin lands on heads. The counter's value changes from $1$ to $2$ and Bessie receives $7$ dollars. Additionally, she gets 10 dollars as a streak bonus.
• In the 3rd coin toss, the coin lands on tails. The counter's value changes from $2$ to $0$.
• In the 4th coin toss, the coin lands on heads. The counter's value changes from $0$ to $1$ and Bessie receives $8$ dollars.
• In the 5th coin toss, the coin lands on heads. The counter's value changes from $1$ to $2$ and Bessie receives $2$ dollars. Additionally, she gets $10$ dollars as a streak bonus.
• In the 6th coin toss, the coin lands on heads. The counter's value changes from $2$ to $3$ and Bessie receives $8$ dollars. Additionally, she gets $1$ dollar as a streak bonus.

In this case, Bessie earns $2 + (7 + 10) + 0 + 8 + (2 + 10) + (8 + 1) = 48$ dollars in total, which is the maximum possible.

Note that streak bonuses are awarded any number of times each time the counter shows $C_i$.

As a side note, if Bessie gets heads in all $6$ coin tosses, she only receives $2 + (7 + 10) + (1 + 1) + 8 + (2 + 5) + 8 = 44$ dollars, which is not the maximum.

SCORING:

• For all inputs: No additional constraints.