/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
数直線上に 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 以下にすることです。
目標を達成するために必要な魔力の総和としてあり得る最小の値を求めてください。
制約
- 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
出力
目標を達成するために必要な魔力の総和の最小値を出力せよ。
入力例 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だけ消費して、操作後の各モンスターの体力は (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 となり、このときが最小となります。
入力例 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
Score : 600 points
Problem Statement
There are N monsters along a number line. At the coordinate i (1\leq i\leq N) is a monster with a stamina of A_i.
Additionally, at the coordinate i, there is a permanent shield of a strength B_i.
This shield persists even when the monster at the same coordinate has a health of 0 or below.
Takahashi, a magician, can perform the following operation any number of times.
- Choose integers l and r satisfying 1\leq l\leq r\leq N.
- Then, consume \max(B_l, B_{l+1}, \ldots, B_r) MP (magic points) to decrease by 1 the stamina of each of the monsters at the coordinates l,l+1,\ldots,r.
When choosing l and r, it is fine if some of the monsters at the coordinates l,l+1,\ldots,r already have a stamina of 0 or below.
Note, however, that the shields at all those coordinates still exist.
Takahashi wants to make the stamina of every monster 0 or below.
Find the minimum total MP needed to achieve his objective.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq A_i,B_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N
Output
Print the minimum total MP needed to achieve his objective.
Sample Input 1
5 4 3 5 1 2 10 40 20 60 50
Sample Output 1
210
Takahashi can achieve his objective as follows.
- Choose (l,r)=(1,5). Consume \max(10,40,20,60,50)=60 MP, and the staminas of the monsters are (3,2,4,0,1).
- Choose (l,r)=(1,5). Consume \max(10,40,20,60,50)=60 MP, and the staminas of the monsters are (2,1,3,-1,0).
- Choose (l,r)=(1,3). Consume \max(10,40,20)=40 MP, and the staminas of the monsters are (1,0,2,-1,0).
- Choose (l,r)=(1,1). Consume \max(10)=10 MP, and the staminas of the monsters are (0,0,2,-1,0).
- Choose (l,r)=(3,3). Consume \max(20)=20 MP, and the staminas of the monsters are (0,0,1,-1,0).
- Choose (l,r)=(3,3). Consume \max(20)=20 MP, and the staminas of the monsters are (0,0,0,-1,0).
Here, he consumes a total of 60+60+40+10+20+20=210 MP, which is the minimum possible.
Sample Input 2
1 1000000000 1000000000
Sample Output 2
1000000000000000000
Sample Input 3
10 522 4575 6426 9445 8772 81 3447 629 3497 7202 7775 4325 3982 4784 8417 2156 1932 5902 5728 8537
Sample Output 3
77917796