题目描述

时间限制：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{p_i}$（$1 \leq i < k$）

要求最大化所选下标的 $a$ 数组元素之和 $\sum{i=1}^k a{p_i}$。

输入格式

1. 第一行：一个正整数 $n$，表示数组长度。
2. 第二行：$n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示数组 $a$。
3. 第三行：$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$