怪物

题目描述

在一条数轴上有 $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。

输入格式

输入按以下格式从标准输入给出:

$N$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$

输出格式

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

样例

5
4 3 5 1 2
10 40 20 60 50

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,这是可能达到的最小值。

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 \le N \le 10^5$
• $1 \le A_i,B_i \le 10^9$
• 输入中的所有值均为整数。