时间限制

1.0 s

内存限制

512.0 MB

题目描述

给定两个长度为 $n$ 的整数数组 $a=[a_1,a_2,\dots,a_n]$ 与 $b=[b_1,b_2,\dots,b_n]$。你需要选择若干下标 $p_1 < p_2 < \dots < p_k$（$1 \leq k \leq n$），满足以下条件：

1. $1 \leq p_i \leq n$（$1 \leq i \leq k$）
2. $p_{i+1} \geq pi + b{pi}$（$1 \leq i < k$） 请在满足上述条件的前提下，最大化 $\sum{i=1}^k a_{p_i}$，即所选下标对应 $a$ 数组元素的总和。

   输入格式

3. 第一行：一个正整数 $n$，表示数组长度。
4. 第二行：$n$ 个非负整数 $a_1,a_2,\dots,a_n$，表示数组 $a$。
5. 第三行：$n$ 个非负整数 $b_1,b_2,\dots,b_n$，表示数组 $b$。

   输出格式

   一行一个整数，表示满足约束条件的最大元素和。

   样例

   样例1输入

   4
   1 2 3 4
   3 3 1 1

   样例1输出

   7

   样例2输入

   6
   1 1 4 5 1 4
   1 2 3 2 1 0

   样例2输出

   11

   数据范围

• 对于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$。