闯关游戏求通关最高总分

问题描述

你来到了一个闯关游戏，该游戏总共有N关，每关都有M个通道，你需要选择一个通道并通往后续关卡：

• 第i个通道可以让你前进a_i关：若当前在第x关，选择第i个通道后将直接来到第x+a_i关，特别地，如果x+a_i ≥ N则直接通关。
• 当你顺利离开第s关时，将获得b_s分。

游戏开始时你在第0关，请问通关时最多能获得多少总分？

输入描述

第一行两个整数N、M，分别表示关卡数量和每关的通道数量。 第二行M个用空格隔开的整数a₀,a₁,…,a_{M-1}，表示每个通道可前进的关数。 第三行N个用空格隔开的整数b₀,b₁,…,b_{N-1}，表示离开对应关卡可获得的分数，保证|b_i| ≤ 10^5。

输出描述

输出一行一个整数，表示通关时最多能够获得的分数。 特别提醒：请勿在输入、输出中附带任何额外提示信息。

样例1

输入

6 2
2 3
1 0 30 100 30 30

输出

131

解释

你可以在第0关选择第1个通道，获得1分并来到第3关；随后选择第0个通道，获得100分并来到第5关；最后任选一个通道，获得30分并通关。总得分1+100+30=131。

样例2

输入

6 2
2 3
1 0 30 100 30 -1

输出

101

解释

部分关卡的得分可能为负数，此时可以选择不经过该关卡以获得更高分数。本样例中从第3关选择前进3关的通道直接通关，总得分1+100=101，优于经过第5关的得分。

数据规模

• 20%的测试点：M=1
• 40%的测试点：N ≤ 20，M ≤ 2
• 100%的测试点：N ≤ 10^4，M ≤ 100，|b_i| ≤ 10^5