题目描述

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

她每次可以执⾏以下任意⼀个操作：

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

2.施法：使⽤最上⽅的符卡，若最上⽅的符卡编号为 $i$ ，则她丢掉卡堆最上⾯的 $L_i$ 张符卡（包括她使⽤的最上⽅的符卡）。她可以对敌⼈造成 $D_i$ 点伤害。如果卡堆不⾜ $L_i$ 张她不能使⽤此操作。

她可以执⾏任意次操作，最后求她的卡堆能造成的最⼤伤害。

输入格式

第⼀⾏包括⼀个正整数 $n$。

第⼆⾏每⾏ $n$ 个正整数 $L_i$。

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

输出格式

⼀⾏⼀个⾮负整数表示卡堆对能造成的最⼤伤害。

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$ 。