配点 : $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$

出力

目標を達成するために必要な魔力の総和の最小値を出力せよ。

5
4 3 5 1 2
10 40 20 60 50

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$ となり、このときが最小となります。

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