伐木业中的卡里拉与迪姆娜

• 时间限制：2 秒
• 内存限制：512 MiB

题目描述

有 $n$ 棵树，高度为 $a_i$。电锯初始有一次电量；每锯一次可使任意树高度减一，之后必须充电。若已完全砍倒的树中最大编号为 $i$，充电费用为 $b_i$。求砍倒全部树的最小总费用。

保证 $a_1=1$，$b_n=0$，$a$ 严格递增且 $b$ 严格递减。

输入格式

第一行一个整数 $n$。第二行输入 $a_1,\ldots,a_n$，第三行输入 $b_1,\ldots,b_n$。

输出格式

输出最小总费用。

样例输入

5
1 2 3 4 5
5 4 3 2 0

样例输出

25

数据范围

对于所有数据，$1\le n\le10^5$，$1\le a_i\le10^9$，$0\le b_i\le10^9$。