题目描述

小z 作为⼀名正统流派的符文师，他带上了他的⼀叠符卡踏上了冒险的旅途。他⼀共有 $n$ 张符卡，他们按照编号顺序从上到下形成⼀叠。每张符卡有两个属性 $L_i$ 和 $D_i$ 。

他每次可以执行以下任意⼀个操作：

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

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

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

输入格式（card.in）

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

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

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

输出格式（card.out）

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

5
2 2 1 1 1
7 8 3 3 3

18

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

82

提示

数据范围

对于 $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 1000000$ 。