Problem Description

You have arrived at a level-based game.

The game consists of a total of $N$ levels, each with $M$ passages. You need to choose one passage to proceed to the next levels. Specifically, the $i$-th passage allows you to advance $a_i$ levels. This means that if you are currently at level $x$, after choosing the $i$-th passage, you will directly reach level $x + a_i$ (notably, if $x + a_i \geq N$, you will have completed the game). Additionally, when you successfully exit level $s$, you will also earn $b_s$ points.

At the start of the game, you are at level $0$. What is the maximum total score you can achieve when you complete the game?

Input Format

The first line contains two integers $N$ and $M$, representing the number of levels and the number of passages per level, respectively.

The next line contains $M$ integers separated by single spaces, $a_0, a_1, \cdots, a_{M-1}$. It is guaranteed that $1 \le a_i \le N$.

The following line contains $N$ integers separated by single spaces, $b_0, b_1, \cdots, b_{N-1}$. It is guaranteed that $|b_i| \le 10^5$.

Output Format

A single line containing an integer, representing the maximum score you can achieve when you complete the game.

Sample Input and Output

Sample Input #1

6 2 
2 3
1 0 30 100 30 30

Sample Output #1

131

Sample Input #2

6 2
2 3
1 0 30 100 30 -1

Sample Output #2

101

Notes

Sample Explanation 1

You can choose the first passage at level $0$, earning $1$ point and reaching level $3$; then choose the second passage, earning $100$ points and reaching level $5$; finally, choose any passage to earn $30$ points and complete the game. Thus, the total score is $1 + 100 + 30 = 131$.

Sample Explanation 2

Note that some levels may have negative scores.

Data Range

For $20\%$ of the test cases, it is guaranteed that $M = 1$.

For $40\%$ of the test cases, it is guaranteed that $N \le 20$ and $M \le 2$.

For all test cases, it is guaranteed that $1 \le N \le 10^4$ and $1 \le M \le 100$.

见题面 Input 部分

见题面 Output 部分