Question
Yet another money game
Alice will toss a coin N times. He also has a counter, which initially shows 0.

Depending on the result of the i- th coin toss, the following happens:
If it heads: counter's value increases by 1 and he gets Xi rupees.
else: resets the counter's value to 0 and gets nothing.

Additionally, there are M kinds of streak bonuses. The i- th kind of streak bonus awards Yi rupees each time the counter shows Ci.

Find the maximum amount of money that alice can receive.
Input
The first line of the input contains 1 integer N.
The next N lines contains N integers Ai, 1, Ai, 2. . Ai, N.

Constraints:
1 <= M <= N <= 5000
1 <= Xi <= 10^9
1 <= Ci <= N
1 <= Yi <= 10^9
C1, C2, …, CM are all different.
Output
Print the maximum amount of money that Alice can receive, as an integer.
Example
Sample Input 1:
6 3
2 7 1 8 2 8
2 10
3 1
5 5

Sample Output 1:
48

Explanation 1:
If he gets head, head, tail, head, head, head, in this order, the following amounts of money are awarded.
1. In the 1- st coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 2 rupees.
2. In the 2- nd coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 7 rupees. Additionally, get 10 rupees as a streak bonus.
3. In the 3- rd coin toss, the coin tails. Change the counter's value from 2 to 0.
4. In the 4- th coin toss, the coin heads. Change the counter's value from 0 to 1 and receive 8 rupees.
5. In the 5- th coin toss, the coin heads. Change the counter's value from 1 to 2 and receive 2 rupees. Additionally, get 10 rupees as a streak bonus.
6. In the 6- th coin toss, the coin heads. Change the counter's value from 2 to 3 and receive 8 rupees. Additionally, get 1 rupee as a streak bonus.
In this case, ALice receives 2+(7+10)+0+8+(2+10)+(8+1)=48 rupees in total, which is the maximum possible.
Note that streak bonuses are awarded any number of times each time the counter shows Ci.
As a side note, if he gets head in all 6 coin tosses, he only receives 2+(7+10)+(1+1)+8+(2+5)+8=44 rupees, which is not the maximum.

Sample Input 2:
3 2
1000000000 1000000000 1000000000
1 1000000000
3 1000000000

Sample Output 2:
5000000000

Online