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

输入 #1

5
4 3 5 1 2
10 40 20 60 50

输出 #1

210

输入输出样例 #2

输入 #2

1
1000000000
1000000000

输出 #2

1000000000000000000

输入输出样例 #3

输入 #3

10
522 4575 6426 9445 8772 81 3447 629 3497 7202
7775 4325 3982 4784 8417 2156 1932 5902 5728 8537

输出 #3

77917796

说明/提示

限制条件

• $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 翻译