题目描述

你正在探索一座地牢，地牢共有 $N$ 层。每一层都有 $M$ 个传送门，你需要选择其中一个传送门前往更深层。其中第 $i$ 个传送门可以让你直接前进 $a_i$ 层，即如果你当前在第 $x$ 层，选择第 $i$ 个传送门后你将到达第 $x+a_i$ 层（特别地，如果 $x + a_i \ge N$，则你成功逃出地牢）。此外，当你顺利离开第 $s$ 层时，你将获得 $b_s$ 个金币。

探险开始时你在第 $0$ 层。请问逃出地牢时最多能获得多少金币。

输入格式

第一行两个整数 $N$、$M$，分别表示地牢层数和每层的传送门数量。

第二行 $M$ 个整数 $a_0,a_1,\cdots,a_{M-1}$，用空格隔开。保证 $1\le a_i \le N$。

第三行 $N$ 个整数 $b_0,b_1,\cdots,b_{N-1}$，用空格隔开。保证 $|b_i|\le 10^5$。

输出格式

一行一个整数，表示逃出地牢时最多能获得的金币数。

样例

6 2 
2 3
1 0 30 100 30 30

131

6 2
2 3
1 0 30 100 30 -1

101

提示

样例解释 1

在第 $0$ 层选择第 $1$ 个传送门，获得 $1$ 金币来到第 $3$ 层；再选择第 $0$ 个传送门，获得 $100$ 金币来到第 $5$ 层；最后任选一个传送门，获得 $30$ 金币逃出地牢。总计 $1+100+30=131$。

样例解释 2

注意某些层的金币可能是负数。

数据范围

对于 $20\%$ 的测试点，保证 $M=1$。

对于 $40\%$ 的测试点，保证 $N \le 20$ 且 $M\le 2$。

对于所有测试点，保证 $1 \le N \le 10^4$，$1 \le M\le 100$。