题目描述

数直線上に $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$

输出格式

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

题目大意

给定 $n$ 以及两个长度为 $n$ 的正整数序列 $A_i,B_i$，你可以执行下述操作任意次：

• 选定任意整数 $l,r$，满足 $1 \le l \le r \le n$。
• 花费 $max_{i=l}^{r} \{B_i\}$ 的代价，将 $A_l,A_{l+1}, \dots A_r$ 中每个都减去 $1$。

请求出使得 $A_i$ 中元素全部 $\le 0$ 所需的最小代价。

$1 \le n \le 10^5, 1 \le A_i,B_i \le 10^9$。

5
4 3 5 1 2
10 40 20 60 50

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

提示

制約

• $1\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ A_i,B_i\ \leq\ 10^9$
• 入力は全て整数

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