C0617 选数

选数

题目描述

给定两个包含 个整数的数组 a=[a₁,...,a_n] 与 b=[b₁,...,b_n] 。你需要指定若干下标 p₁<...k（1≤k≤n）使得以下条件成立：

• 1 ≤ p_i ≤ n（1 ≤ i ≤ k）；
• p_i+1 ≥ p_i + b_pi（1 ≤ i ≤ k）

你需要在满足以上条件的前提下最大化 Σ(k,i=1)，也即最大化数组 a 对应下标的整数之和。

输入

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

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

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

输出

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

数据范围

对于所有测试点，保证2≤n≤10^5,0≤ai≤10^9,0≤bi≤n

输入样例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