【题目描述】

感谢你为ysc写出了打boss的程序！但是糊涂蛋ysc突然想起来在打boss前还有个更重要的事，他现在和boss不在一个地图！。

为了方便你的编程，ysc把jx3的地图暴力拆解成了一个有n个城市的地图，对于每个城市i只与城市i+1之间存在一条双向道路（既与i相连的城市只有i+1，i-1，编号为1和n的城市除外），通过这条道路需要花费ysc的时间为  ai，每个城市之间存在一位跨城市交通的车夫，车夫可以直接把你送到别的城市而不花费时间，每个城市的车夫的传送半径为 ki（既在i城市的车夫可以把你送到 i+ki 城市，并且不花费时间）如果目标城市大于n则为n。

ysc现在在1号城市，而他需要到n号城市去打boss，并且由于他的贫穷，他在赶路过程中只能使用一次车夫，为了不因为赶路而错过首甲，请你写一个程序告诉他他所需要花费的总时间。

【输入格式】

输入数据包括三行

第一行一个整数n，表示城市数。

第二行n-1个数，表示第i个ai。

第三行n个数，第i个表示城市的车夫的传送半径ki。

【输出格式】

一行一个整数，表示他所花费的时间。

【输入样例】

4 1 2 3 0 0 0 0

【输出样例】

6

【数据范围与提示】

对于50%的数据：1≤n≤310^3，1≤ai≤1×10^5，0≤ki≤3×10^3。

对于100%的数据：1≤n≤310^6，1≤ai≤1×10^12，0≤ki≤3×10^6。