题目描述

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、关怀大佬