P10108 [GESP202312 Level 6] Level-Clearing Game

Related multiple-choice and true/false questions: .

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?

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 one integer in one line, representing the maximum score you can obtain when you clear the game.

**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