分数: 600 点
问题陈述
有 N 数轴上的怪物。在坐标处 i (1\leq i\leq N) 是一个耐力为 A_i.
另外,在坐标处 i,有一个强度的永久护盾 B_i.
即使同一坐标的怪物的生命值为 0 或以下。
高桥,一名魔术师,可以执行任意次数的以下操作。
- 选择整数 l 和 r 满意 1\leq l\leq r\leq N.
- 然后,消费 \max(B_l, B_{l+1}, \ldots, B_r) MP(魔法点)减少 1 坐标处每个怪物的体力 l,l+1,\ldots,r.
选择时 l 和 r,如果坐标处有一些怪物就好了 l,l+1,\ldots,r 已经有耐力 0 或以下。
但请注意,所有这些坐标处的护盾仍然存在。
高桥想要提高每个怪物的耐力 0 或以下。
找出实现目标所需的最低总 MP 数。
约束
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 10^9
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
输出
打印实现其目标所需的最低 MP 总量。
示例输入 1
5 4 3 5 1 2 10 40 20 60 50
示例输出 1
210
高桥可以通过以下方式实现他的目标。
- 选择 (l,r)=(1,5)。消费 \max(10,40,20,60,50)=60 MP,怪物的体力为 (3,2,4,0,1).
- 选择 (l,r)=(1,5)。消费 \max(10,40,20,60,50)=60 MP,怪物的体力为 (2,1,3,-1,0).
- 选择 (l,r)=(1,3)。消费 \max(10,40,20)=40 MP,怪物的体力为 (1,0,2,-1,0).
- 选择 (l,r)=(1,1)。消费 \max(10)=10 MP,怪物的体力为 (0,0,2,-1,0).
- 选择 (l,r)=(3,3)。消费 \max(20)=20 MP,怪物的体力为 (0,0,1,-1,0).
- 选择 (l,r)=(3,3)。消费 \max(20)=20 MP,怪物的体力为 (0,0,0,-1,0).
在这里,他总共消耗了 60+60+40+10+20+20=210 MP,这是可能的最小值。
示例输入 2
1 1000000000 1000000000
示例输出 2
1000000000000000000
示例输入 3
10 522 4575 6426 9445 8772 81 3447 629 3497 7202 7775 4325 3982 4784 8417 2156 1932 5902 5728 8537
示例输出 3
77917796