建筑师 Hrvoje 被要求画一面由垂直柱子组成的大型不规则墙壁。
墙壁由 $n$ 个相邻的柱子组成，其中第 $i$ 个柱子的高度为 $a_i$，宽度为 $1$。为了使图纸尽可能复杂，第 $i$ 个柱子被等分成 $b_i$ 个高度相等的部分。
Hrvoje 手头只有一把直尺和一支铅笔。他每画一笔可以画出一条线段（两点之间的直段）而无需抬起铅笔。他的目标是使用尽可能少的线段画出整面墙，包括所有柱子的边缘以及它们等分部分之间的所有分界线。
对于给定的墙壁，输出完整画出该墙壁所需的最少线段数。
输入格式
第一行包含一个正整数 $n$（$1 \le n \le 10^5$），表示题目描述中的数量。
第二行包含一个由 $n$ 个数组成的序列 $1 \le a_i \le 10^9$，表示题目描述中的高度。
第三行包含一个由 $n$ 个数组成的序列 $1 \le b_i \le 10^9$，表示题目描述中的等分数。
输出格式
在第一行也是唯一的一行中输出一个整数——Hrvoje 画出这面墙所需的最少线段数。
子任务
| 子任务 | 分值 | 数据范围 |
|---|---|---|
| 1 | 11 | $N = 1$ |
| 2 | 13 | $N = 2, 1 \le a_i, b_i \le 10$ |
| 3 | 29 | $1 \le a_i \le 10^6$，对于每个 $1 \le i \le n$，$b_i$ 整除 $a_i$ |
| 4 | 57 | 无附加限制。 |
样例
输入 1
3 4 6 4 2 3 4
输出 1
10
输入 2
3 4 6 3 3 3 2
输出 2
12
说明
第二个样例的解释：Hrvoje 将把第一个柱子中最顶端的线段延伸到第二个柱子中，从而将 2 条线段“合并”为 1 条。他将对墙壁底部的 3 条线段进行相同的操作。这样，他总共将画出 12 条线段，可以证明这是 Hrvoje 需要画出的最少线段数。