Ex - Monster
当前没有测试数据。
Ex - 怪物
得分：$600$ 分
问题描述
一条数轴上有 $N$ 个怪物。在坐标 $i$ $(1\leq i\leq N)$ 处有一个耐力为 $A_i$ 的怪物。
此外，在坐标 $i$ 处，有一个持久的防御力为 $B_i$ 的护盾。
当怪物的生命值为 $0$ 或者小于 $0$ 时，这个护盾仍然存在。
一个名叫 Takahashi 的魔法师可以进行以下操作任意多次。
- 选择整数 $l$ 和 $r$，满足 $1\leq l\leq r\leq N$。
- 然后，消耗 $\max(B_l, B_{l+1}, \ldots, B_r)$ 魔法点数 (MP)，使得坐标为 $l,l+1,\ldots,r$ 的每个怪物的耐力减少 $1$。
在选择 $l$ 和 $r$ 时，如果坐标为 $l,l+1,\ldots,r$ 的怪物中有一些怪物的耐力已经为 $0$ 或者小于 $0$，也是可以的。
然而，请注意，所有这些坐标上的防御力仍然存在。
Takahashi 希望将每个怪物的耐力降低到 $0$ 或者小于 $0$。
找出达到他目标的最小总 MP。
约束条件
- $1 \leq N \leq 10^5$
- $1 \leq A_i,B_i \leq 10^9$
- 输入中的所有值都是整数。
输入
输入以以下格式从标准输入给出：
输出
输出达到他目标的最小总 MP。
5
4 3 5 1 2
10 40 20 60 50
210
Takahashi 可以通过以下方式实现他的目标。
- 选择 $(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，这是可能的最小值。
1
1000000000
1000000000
1000000000000000000
10
522 4575 6426 9445 8772 81 3447 629 3497 7202
7775 4325 3982 4784 8417 2156 1932 5902 5728 8537
77917796