题目背景

2023 年 12 月 GESP C++ 六级编程第 1 题

题目描述

游戏共有 $N$ 关，每关都有 $M$ 个通道。第 $i$ 个通道会让你前进 $a_i$ 关；若当前在第 $x$ 关，选择该通道后会来到第 $x+a_i$ 关；若 $x+a_i \ge N$，则直接通关。

当你顺利离开第 $s$ 关时，会获得 $b_s$ 分。游戏开始时你在第 $0$ 关。请计算通关时最多能获得多少总分。

输入格式

第一行输入两个整数 $N,M$。 第二行输入 $M$ 个整数 $a_0,a_1,ldots,a_{M-1}$。 第三行输入 $N$ 个整数 $b_0,b_1,ldots,b_{N-1}$。

输出格式

输出一行一个整数，表示通关时最多能够获得的总分。

6 2
2 3
1 0 30 100 30 30

131

6 2
2 3
1 0 30 100 30 -1

101

数据范围与提示

• 对于 $20$ 的测试点，保证 $M=1$。
• 对于 $40$ 的测试点，保证 $N \le 20$，$M \le 2$。
• 对于全部测试点，$N \le 10^4$，$M \le 100$，$1 \le a_i \le N$，$|b_i|\le 10^5$。
• 得分可能为负数。

来源

GESP 2023 年 12 月 C++ 六级 T1