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.

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.

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

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