给定两个包含 n 个整数的数组 a=[a_1,\dots,a_n] 与 b=[b_1,\dots,b_n]。你需要指定若干下标 p_1\lt \cdots\lt p_k（1\leq k\leq n）使得以下条件成立：

• 1\leq p_i\leq n（1\leq i\leq k）；
• p_{i+1}\geq p_i+b_{p_i}（1\leq i< k）。

你需要在满足以上条件的前提下最大化 \sum_{i=1}^k a_{p_k}，也即最大化数组 a 对应下标的整数之和。

第一行，一个正整数 n，表示数组长度。

第二行，n 个正整数 a_1,a_2,\dots,a_n，表示数组 a。

第三行，n 个正整数 b_1,b_2,\dots,b_n，表示数组 b。

一行，一个整数，表示在满足下标条件的前提下，数组 a 对应下标的整数之和的最大值。

说明/提示

对于 40\% 的测试点，保证 2\leq n\leq 10^3。

对于所有测试点，保证 2\leq n\leq 10^5，0\leq a_i\leq 10^9，0\leq b_i\leq n。

GESP六级26年3月动态规划