题目描述

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

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

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

输入格式

输入数据包括三行

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

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

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

输出格式

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

样例

input1

4 1 2 3 0 0 0 0

output1

6

限制与提示

对于50%的数据：$1 \le n\le 3 \times 10^3$，$1 \le a_i \le 1 \times 10^5$，$0 \le k_i \le 3 \times 10^3$。

对于100%的数据：$1 \le n \le 1 \times 10^6$，$1 \le a_i \le 1 \times 10^{12}$，$0 \le k_i \le 1 \times 10^6$。