#P18151. Optimal Train Operation

Optimal Train Operation

Optimal Train Operation

UTPC 铁路有一条笔直的线路,共有 N+1N+1 个车站,从起点站到终点站依次编号为 0,1,…,N0,1,\dots,N。对每个 0≤i≤N−10\le i\le N-1,车站 ii 与 i+1i+1 相邻,这两站之间的拥堵度为 CiC_i。目前,车辆基地设在车站 00 和 NN。

在下一次运行图调整中,会重复执行以下操作来修建车辆基地:

  • 选择一个车站 ii(1≤i≤N−11\le i\le N-1),在那里修建车辆基地,花费 AiA_i。

之后,会重复执行以下操作来开行列车:

  • 选择两个已经建有车辆基地的车站 l<rl<r,在它们之间开行一列列车。该操作会把区间 [l,r)[l,r) 内每一段的拥堵度减 1,花费 r−lr-l。

目标是让每一段的拥堵度都降到 0 或以下。求最小总花费。

输入格式

第一行一个整数 NN(2≤N≤5⋅1052\le N\le 5\cdot 10^5)。

第二行 NN 个整数 C0,C1,…,CN−1C_0,C_1,\dots,C_{N-1}(1≤Ci≤1091\le C_i\le 10^9)。

第三行 N−1N-1 个整数 A1,A2,…,AN−1A_1,A_2,\dots,A_{N-1}(1≤Ai≤1091\le A_i\le 10^9)。

输出格式

输出一个整数,表示最小总花费。

样例 1

输入:

4
3 1 4 1
5 9 2

输出:

15

在车站 3 修建车辆基地,开行 3 列 0→30\to3 的列车和 1 列 0→40\to4 的列车,总花费为 2+3⋅3+4=152+3\cdot3+4=15。

样例 2

输入:

9
28 35 19 27 84 98 78 79 60
40 35 54 63 72 71 27 94

输出:

682