题面描述

你作为一名正统流派的符文师，你带上了你的一叠符卡踏上了冒险的旅途。

你一共有 $n$ 张符卡，他们按照编号顺序从上到下形成一叠。每张符卡有两个属性 $L_i$ 和 $D_i$。

你每次可以执行以下任意一个操作：

1.切换：把卡堆最上方的符卡放到卡堆底。

2.施法：使用最上方的符卡，若最上方的符卡编号为$i$，则你丢掉卡堆最上面的 $L_i$ 张符卡（包括你使用的最上方的符卡）。你可以对敌人造成 $D_i$点伤害。如果卡堆不足 $L_i$ 张你不能使用此操作。

你可以执行任意次操作，最后求你的卡堆能造成的最大伤害。

输入格式

第一行包括一个正整数 $n$。

第二行每行 $n$ 个正整数 $L_i$。

第三行每行 $n$ 个正整数 $D_i$。

输出格式

一行一个非负整数表示你的卡堆对能造成的最大伤害。

样例

输入1

5
2 2 1 1 1 
7 8 3 3 3

输出1

18

输入2

20
4 2 3 3 4 2 3 2 3 3 4 3 3 2 3 2 1 2 4 2
15 8 7 8 16 2 14 8 4 5 9 13 5 2 3 8 1 3 9 3

输出2

82

样例解释

样例1：切换，施法，施法，切换，施法，最后打出编号为1，2，3的牌。

样例2：略

数据规模

对于 $30\%$ 的数据: $1 \leq n \leq 10$

对于 $50\%$ 的数据：$1 \leq n \leq 20$。

对于 $70\%$ 的数据：$1 \leq n \leq 100$。

对于 $100\%$ 的数据: $1 \leq L_i \leq n \leq 1000, 1 \leq D_i \leq 10^6$。

时间限制：1S

空间限制：256MB