Maximum Score in a Level-Based Game

You are playing a challenging level-based game. The game consists of $N$ levels and each level has $M$ channels. When you are at level $x$, you choose one of the $M$ channels. The $i$-th channel will advance you by $a_i$ levels, i.e. you will move from level $x$ to level $x+a_i$. In particular, if $x+a_i \ge N$, then you have completed the game.

Additionally, when you leave level $s$, you gain $b_s$ points. You start the game at level $0$. Your task is to determine the maximum total score you can achieve by completing the game.

inputFormat

The input consists of three lines:

• The first line contains two integers $N$ and $M$, representing the total number of levels and the number of channels per level.
• The second line contains $M$ integers: $a_0, a_1, \ldots, a_{M-1}$, where $a_i$ denotes the number of levels advanced if you choose the $i$-th channel.
• The third line contains $N$ integers: $b_0, b_1, \ldots, b_{N-1}$, where $b_s$ is the score you obtain when leaving level $s$.

outputFormat

Output a single integer, the maximum total score you can accumulate upon completing the game.

sample

5 2
1 3
1 2 3 4 5

15