Problem Description

给定两个包含 n 个整数的数组 a = [a1, ..., an] 与 b = [b1, ..., bn]。你需要指定若干下标 p1 < ... < pk (1 <= k <= n) 使得以下条件成立：

* 1 <= p[i] <= n (1 <= i <= k)；
* p[i+1] >= p[i] + b[p[i]] (1 <= i < k)。

你需要在满足以上条件的前提下最大化 a[p1] + ... + a[pk]，也即最大化数组 a 对应下标的整数之和。

Input Format

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

第二行，n 个正整数 a1, a2, ..., an，表示数组 a。

第三行，n 个正整数 b1, b2, ..., bn，表示数组 b。

Output Format

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

4
1 2 3 4
3 3 1 1

7

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

11

Hint

对于 40% 的测试点，保证 2 <= n <= 1000。

Source

QingdaoOJ Problem Generator