AT_utpc2023_o.Optimal Train Operation

UT 铁道 PC 本线沿着一条线路设有 $N+1$ 个车站，编号依次为 $0,1,\ldots,N$，从起点站到终点站。对于每个 $i$ $(0\leq i\leq N-1)$，站 $i$ 与站 $i+1$ 相邻，这两站之间的拥挤度为 $C_i$。目前，站 $0$ 和站 $N$ 已经设有车辆基地。

在接下来的列车运行图修改中，你可以多次执行以下操作来建设新的车辆基地：

• 选择某个 $i$ $(1\leq i\leq N-1)$，在站 $i$ 设立车辆基地，耗费 $A_i$ 的花费。

然后，你可以多次执行以下操作，在车辆基地之间运行列车：

• 选择设有车辆基地的车站 $l,r$ $(l<r)$，在它们之间运行 $1$ 列列车。此时，所有满足 $l\leq i < r$ 的区间 $(i,i+1)$ 的拥挤度减少 $1$。花费为 $r-l$。

你的目标是保证所有 $i$ $(0\leq i\leq N-1)$，站 $i$ 与站 $i+1$ 之间的拥挤度都不大于 $0$。请你求出建设车辆基地和运行列车所需的最小总花费。

输入通过标准输入给出，格式如下：

$N$ $C_0$ $C_1$ $\ldots$ $C_{N-1}$ $A_1$ $A_2$ $\ldots$ $A_{N-1}$

请输出一行，表示最小总花费。

样例解释 1

在站 $3$ 建设车辆基地，分别在 $0,3$ 区间运行 $3$ 次列车，在 $0,4$ 区间运行 $1$ 次列车。这样，每个区间的拥挤度都不大于 $0$，总花费为 $15$。

数据范围

• 所有输入均为整数。
• $2 \leq N \leq 5\times 10^5$
• $1 \leq C_i \leq 10^9$ $(0\leq i\leq N-1)$
• $1 \leq A_i \leq 10^9$ $(1\leq i\leq N-1)$

由 ChatGPT 5 翻译