灯带

• 时间限制：$2$ 秒
• 空间限制：$512\ \mathrm{MB}$

题目描述

一条地下疏散通道依次安装了 $n$ 盏应急灯。为了在断电时尽可能提供充足照明，控制系统要为每盏灯选择一个亮度级别。第 $i$ 盏灯的级别记为非负整数 $b_i$，受灯具额定功率限制，必须满足

通道各处的墙面反光率不同。如果相邻两盏灯的亮度差过大，人眼在移动时会短暂失去对暗处的辨认能力。因此，第 $i$ 盏灯和第 $i+1$ 盏灯之间设置了一个渐变限制 $d_i$，要求

所有灯的级别会在应急状态启动前一次性设定，不考虑启动后的动态调节。在满足每盏灯的上限与所有相邻渐变限制的前提下，管理人员希望总照明强度尽可能大。

请求出 $\sum_{i=1}^{n}b_i$ 的最大值。只需输出最大总亮度，不需要构造具体设置方案。

输入格式

第一行一个正整数 $n$，表示灯的数量。

第二行 $n$ 个非负整数 $a_1,a_2,\ldots,a_n$，表示每盏灯的亮度上限。

当 $n>1$ 时，第三行有 $n-1$ 个非负整数 $d_1,d_2,\ldots,d_{n-1}$，表示相邻灯之间允许的最大亮度差。当 $n=1$ 时，输入没有第三行。

输出格式

输出一行一个非负整数，表示亮度总和的最大值。

输入样例 1

5
8 5 9 9 3
2 1 3 2

输出样例 1

26

输入样例 2

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

输出样例 2

46

输入样例 3

见附件 sample/glow3.in

输出样例 3

见附件 sample/glow3.out

样例说明

样例 $1$ 中，可以将五盏灯的亮度依次设为 $7,5,6,5,3$，亮度总和为 $26$。不存在总亮度更大的合法设置。

数据范围

对于所有测试点，$1\le n\le 10^6$，$0\le a_i,d_i\le 10^9$。