测试数据来自 b6e0_OJ/1013

题目描述

b6e0看见了一段楼梯。这段楼梯有$n$阶，他现在在第$0$阶，他想要到第$n$阶。
对于所有$i$($1\le i\le n$)，可以从第$a_i$阶~第$i-1$阶直接跨到第$i$阶。每一阶还有一个值$b_i$，表示从$j$到$i$($j<i$)花费$b_j+b_i$的体力。特殊地，$b_0=0$。
b6e0想知道他到达第$n$阶花费的最少体力是多少。

输入格式

第一行输入整数$n$，表示这段楼梯有$n$阶。
第二行输入$n$个整数，第$i$个数表示$a_i$。
第三行输入$n$个整数，第$i$个数表示$b_i$。
输入保证正确，不用判错。

输出格式

输出到达第$n$阶花费的最少体力。

输入输出样例1

输入

5
0 1 2 3 4
1 2 3 4 5

输出

25

输入输出样例2

输入

10
0 0 2 3 1 4 6 6 6 1
100000 5 4 3 2 1 99 98 100 10000

输出

10010

样例解释

对于样例一，唯一的一条路线是$0$->$1$->$2$->$3$->$4$->$5$，花费为$1+(1+2)+(2+3)+(3+4)+(4+5)=25$。

数据范围

对于100%的数据，$1\le n\le5\times10^5$。对于所有$i$($1\le i\le n$)，$0\le a_i<i$，$-10^9\le b_i\le10^9$。
Subtask 1(15pts): $n\le10$。
Subtask 2(25pts): $n\le1000$。
Subtask 3(10pts): 对于所有$i$($2\le i\le n$)，$b_{i-1}\le b_i$。
Subtask 4(10pts): 对于所有$i$($2\le i\le n$)，$a_{i-1}\le a_i$。
Subtask 5(10pts): 对于所有$i$($1\le i\le n$)，$1\le b_i\le10^9$。
Subtask 6(30pts): 无特殊限制。

贡献者

题面，数据:b6e0
核题:Ducati、关怀大佬