Migrated from Lutece 3257 砍树

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

卡里拉被公司派去丛林里砍树。现在她的面前有 $n$ 棵树，标号为 $1$ 到 $n$ ，标号为 $i$ 的树的硬度为 $a_i$ ，奖励值为 $b_i$ ，题目保证对于 $i < j$ ，有 $a_i<a_j$ 且 $b_i>b_j$ ，还保证 $a_1=1$ ， $b_n=0$ 。

卡里拉希望尽快把所有的树都砍倒。对于硬度为 $a_i$ 的树，卡里拉需要砍 $a_i$ 下能把这棵树砍倒，砍树的时间可以忽略不记，然而由于卡里拉的体力并不好，每砍一下后她都需要休息一段时间，具体来说，如果砍完一下后所有已经被砍倒的树的 $b$ 值的最小值为 $b_m$（初始时 $b_m=10^{10^{10^{10}}}$） ，那么她就需要休息 $b_m$ 分钟才能砍下一次。

现在请你告诉她，她需要多少分钟才能把 $n$ 棵树都砍倒。

Input

第一行一个正整数 $n$ ，代表树的数量。 第二行 $n$ 个正整数 $a_i$ ，代表树的硬度。 第三行 $n$ 个正整数 $b_i$ ，代表树的奖励值。

Output

一行一个正整数，代表砍倒所有树需要的分钟数。

Samples

5
1 2 3 4 5
5 4 3 2 0

25

6
1 2 3 10 20 30
6 5 4 3 2 0

138

Constraints

$1 \le n \le 10^5$ $1 \le a_i \le 10^9$ $1 \le b_i \le 10^9$

Note

对于样例一，我们可以先砍一次第一棵树，然后再砍五次第五棵树，再砍其他的树，这种方案的花费为 $1\times5+4\times5+1\times0+2\times0+3\times0+4\times0=25$。

请注意，在砍倒第五树时 $b_m=0$。