问题描述

数轴上有 $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)$ 魔法点（MP），将坐标 $l, l+1, \\ldots, r$ 处的每个怪物的耐力减少 $1$。

在选择 $l$ 和 $r$ 时，如果坐标 $l, l+1, \\ldots, r$ 处的一些怪物的耐力已经为 $0$ 或更低，则也是可以的。
但请注意，所有这些坐标处的护盾仍然存在。

高桥想要使每只怪物的耐力为 $0$ 或更低。
找出实现他的目标所需的最小总 MP。

约束条件

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

输出

输出实现他的目标所需的最小总 MP。

样例输入 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$ 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，这是可能的最小值。

样例输入 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