题目描述

给定两个包含 n 个整数的数组 a=[a_1,…,a_n] 与 b=[b_1,…,b_n]。你需要指定若干下标 p_1,…,p_k（1≤p_1<p_2<…<p_k≤n），使得对于相邻选择的下标 p_j,p_{j+1}，满足 p_{j+1}≥p_j+b_{p_j}。

你需要在满足以上条件的前提下最大化所选下标对应的 a 值之和，也即最大化 Σ a_{p_j}。

输入格式

第一行，一个正整数 n，表示数组长度。第二行 n 个非负整数 a_1,…,a_n，表示数组 a。第三行 n 个非负整数 b_1,…,b_n，表示数组 b。

输出格式

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

样例

样例输入 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≤n≤10^3；对于所有测试点，保证 2≤n≤10^5，0≤a_i≤10^9，0≤b_i≤n。