P6170 - [GESP202312 六级] 闯关游戏 - ZUFEOJ

内存限制：256 MB 时间限制：2 S

题面：Markdown 评测方式：文本比较上传者：

提交：1 通过：1

提交提交记录统计 Web Board

你来到了一个闯关游戏。这个游戏总共有 N 关，每关都有 M 个通道，你需要选择一个通道并通往后续关卡。其中，第 i 个通道可以让你前进 ai 关，也就是说，如果你现在在第 x 关，那么选择第 i个通道后，你将直接来到第 x+aii关（特别地，如果 x+ai≥N，那么你就通关了）。此外，当你顺利离开第 s 关时，你还将获得 bs分。游戏开始时，你在第 0 关。请问，你通关时最多能获得多少总分。

第一行两个整数 N，M，分别表示关卡数量和每关的通道数量。接下来一行 M 个用单个空格隔开的整数 a0,a1⋯,aM-1。保证 1≤ai≤N。接下来一行 N 个用单个空格隔开的整数 b0,b1⋯,bN-1。保证 ∣bi∣≤105。

<span style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;">一行一个整数，表示你通关时最多能够获得的分数。</span>

6 2
2 3
1 0 30 100 30 -1

<p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> <span style="font-weight:bolder;">样例解释 1</span> <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> 你可以在第 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">0</span></span></span> 关选择第 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">1</span></span></span> 个通道，获得 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">1</span></span></span> 分并来到第 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">3</span></span></span> 关；随后再选择第 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">0</span></span></span> 个通道，获得 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">100</span></span></span> 分并来到第 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">5</span></span></span> 关；最后任选一个通道，都可以获得 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord">30</span></span></span> 分并通关。如此，总得分为 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.0833em;"></span><span class="mord">1</span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.0833em;"></span><span class="mord">100</span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span><span class="strut"></span><span class="mord">30</span><span class="mspace"></span><span class="mrel">=</span><span class="mspace"></span><span class="strut"></span><span class="mord">131</span></span></span>。 <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> <span style="font-weight:bolder;">样例解释 2</span> <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> 请注意，一些关卡的得分可能是负数。 <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> <span style="font-weight:bolder;">数据范围</span> <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> 对于 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.0556em;"></span><span class="mord">20%</span></span></span> 的测试点，保证 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut"></span><span class="mord mathnormal" style="font-family:KaTeX_Math;font-style:italic;">M</span><span class="mspace"></span><span class="mrel">=</span><span class="mspace"></span><span class="strut"></span><span class="mord">1</span></span></span>。 <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> 对于 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.0556em;"></span><span class="mord">40%</span></span></span> 的测试点，保证 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord mathnormal" style="font-family:KaTeX_Math;font-style:italic;">N</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut"></span><span class="mord">20</span></span></span>；保证 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord mathnormal" style="font-family:KaTeX_Math;font-style:italic;">M</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut"></span><span class="mord">2</span></span></span>。 <br /> <p style="color:#404040;font-family:-apple-system,font-size:16px;background-color:#FFFFFF;"> 对于所有测试点，保证 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord mathnormal" style="font-family:KaTeX_Math;font-style:italic;">N</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut"></span><span class="mord">1</span><span class="mord"><span class="mord">0</span><span class="msupsub"><span class="vlist-t"><span class="vlist-r"><span class="vlist" style="vertical-align:bottom;"><span><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight" style="font-size:0.7em;"><span class="mord mtight">4</span></span></span></span></span></span></span></span></span></span>；保证 <span class="katex" style="font-size:1.21em;line-height:1.2;font-family:KaTeX_Main,;"><span class="katex-html"><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord">1</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut" style="vertical-align:-0.136em;"></span><span class="mord mathnormal" style="font-family:KaTeX_Math;font-style:italic;">M</span><span class="mspace"></span><span class="mrel">≤</span><span class="mspace"></span><span class="strut"></span><span class="mord">100</span></span></span>。 <br />