选数

题目描述

给定两个包含 n 个整数的数组 A 与 B。你需要指定若干下标 i(1) < i(2) < ... < i(k)，使得选出的任意两个下标 p, q（p < q）满足 i(q) ≥ i(p) + B[i(p)]。 你需要在满足以上条件的前提下最大化选出的 A 数组中对应下标的整数之和。

输入格式

第一行，一个正整数 n，表示数组长度。 第二行，n 个非负整数，表示数组 A。 第三行，n 个非负整数，表示数组 B。

输出格式

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

样例

输入

4
1 2 3 4
3 3 1 1

输出

7

数据范围

对于所有测试点，保证 1 ≤ n ≤ 100000，0 ≤ A[i], B[i] ≤ 100000。