1561: 符文师

【题目描述】

小智作为一名正统流派的符文师，她带上了她的一叠符卡踏上了冒险的旅途。她一共有n张符卡，他们按照编号顺序从上到下形成一叠。

每张符卡有两个属性Li和Di。

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

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

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

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

【输入格式】

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

第二行每行n个正整数Li。

第三行每行n个正整数Di。

【输出格式】

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

【输入样例一】

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≤n≤10。

对于50%的数据，满足1≤n≤20。

对于70%的数据，满足1≤n≤100。

对于100%的数据，满足1≤Li≤n≤1000,1≤Di≤1000000。

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

第二行每行n个正整数Li。

第三行每行n个正整数Di。

5

2 2 1 1 1

7 8 3 3 3

18