问题描述

haopp正在进行闯关游戏，当haopp身处第$i$关的时候，haopp需要花费$a_i$兵力进行闯关，当haopp通过第$i$关后，haopp可以跳转到第$k$关，其中$i+1\leq k\leq i+t_i$。

例如haopp身处第5关，且$a_5=5$,$t_5=7$,那么他可以花费5兵力且下一关跳转到第$k$关,$6\leq k\leq12$。

刚开始haopp在第一关。

输入格式

第一行输入一个正整数 $n$

第二行输入 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$ 。

第三行输入 $n$ 个正整数，第 $i$ 个正整数代表 $t_i$ 。

输出格式

输出一个正整数代表 pp需要到达第n+1关最少需要多少兵力。

样例输入1

5 
1 2 3 4 5
5 4 3 2 1

样例输出1

1

样例1解释

haopp通过第一关花费1兵力后直接跳到第6关

样例输入2

5
1 1 1 1 1
1 2 3 2 1

样例输出2

3

样例2解释

haopp分别通过关卡1,2,4然后跳到关卡6

样例输入3

10
0 1 2 3 4 5 6 7 8 9
1 2 1 2 2 1 2 1 2 1

样例输出3

22

说明/提示

对于所有评测数据，$1\leq n\leq10^6，0 \leq a_i \leq10^9，1 \leq t_i \leq15$。