AT_abc275_h [ABC275Ex] Monster

在数轴上有 $N$ 只怪兽排成一列，坐标 $i$ 处（$1\leq i\leq N$）有一只体力为 $A_i$ 的怪兽。 此外，坐标 $i$ 处始终存在强度为 $B_i$ 的屏障。 即使该坐标上的怪兽体力降为 $0$ 或以下，该屏障依然存在。 作为魔法使的高桥君可以进行如下操作任意多次： - 选择满足 $1\leq l\leq r\leq N$ 的整数 $l,r$。 - 消耗 $\max(B_l,B_{l+1},\ldots,B_r)$ 的魔力，使得坐标 $l,l+1,\ldots,r$ 上的所有怪兽体力减少 $1$。 选择 $l,r$ 时，即使区间 $l,l+1,\ldots,r$ 中已经存在体力为 $0$ 或以下的怪兽也没有关系。 但请注意，即使如此，各坐标上的屏障依然不会消失。 高桥君的目标是让所有怪兽的体力都降为 $0$ 或以下。 请你求出达成目标所需魔力总和的最小可能值。

输入以如下格式从标准输入给出。 > $N$ $A_1$ $A_2$ $\ldots$ $A_N$ $B_1$ $B_2$ $\ldots$ $B_N$

输出达成目标所需魔力总和的最小值。

## 限制条件 - $1\leq N\leq 10^5$ - $1\leq A_i,B_i\leq 10^9$ - 输入均为整数 ## 样例解释 1 高桥君可以按如下方式进行操作以达成目标： - 选择 $(l,r)=(1,5)$，消耗魔力 $\max(10,40,20,60,50)=60$，操作后各怪兽体力为 $(3,2,4,0,1)$。 - 选择 $(l,r)=(1,5)$，消耗魔力 $\max(10,40,20,60,50)=60$，操作后各怪兽体力为 $(2,1,3,-1,0)$。 - 选择 $(l,r)=(1,3)$，消耗魔力 $\max(10,40,20)=40$，操作后各怪兽体力为 $(1,0,2,-1,0)$。 - 选择 $(l,r)=(1,1)$，消耗魔力 $\max(10)=10$，操作后各怪兽体力为 $(0,0,2,-1,0)$。 - 选择 $(l,r)=(3,3)$，消耗魔力 $\max(20)=20$，操作后各怪兽体力为 $(0,0,1,-1,0)$。 - 选择 $(l,r)=(3,3)$，消耗魔力 $\max(20)=20$，操作后各怪兽体力为 $(0,0,0,-1,0)$。 此时消耗的魔力总和为 $60+60+40+10+20+20=210$，且这是最小值。 由 ChatGPT 4.1 翻译