Background

Related multiple-choice and true/false questions: https://ti.luogu.com.cn/problemset/1138.

Problem Description

You have arrived at a level-clearing game.

This game has a total of $N$ levels. Each level has $M$ passages. You need to choose one passage to move to later levels. The $i$-th passage lets you move forward by $a_i$ levels. That is, if you are currently at level $x$, then after choosing the $i$-th passage, you will go directly to level $x+a_i$ (in particular, if $x + a_i \geq N$, then you clear the game). Also, when you successfully leave level $s$, you will gain $b_s$ points.

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

Input Format

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

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

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

Output Format

Output one integer in one line, representing the maximum score you can obtain when you clear the game.

6 2 
2 3
1 0 30 100 30 30

131

6 2
2 3
1 0 30 100 30 -1

101

Hint

Sample Explanation 1

You can choose the $1$-st passage at level $0$, gain $1$ point, and arrive at level $3$. Then choose the $0$-th passage, gain $100$ points, and arrive at level $5$. Finally, choose any passage, and you can gain $30$ points and clear the game. In this way, the total score is $1+100+30=131$.

Sample Explanation 2

Note that the scores of some levels may be negative.

Constraints

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

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

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

Translated by ChatGPT 5