题目背景

本题满分 $110$。

题目描述

建筑师 Hrvoje 需要画出一堵由竖直柱子组成的不规则墙。

墙由 $n$ 根紧挨着摆放的柱子组成，第 $i$ 根柱子的高度为 $a_i$，宽度为 $1$。为了让图更复杂，第 $i$ 根柱子会被水平等分为 $b_i$ 段（每段高度相等）。

Hrvoje 只有直尺和铅笔。他一次落笔可以画出一条线段（两个点间的直线），且画线段过程中不能抬笔。目标是用尽可能少的线段画出整堵墙，包括：

• 所有柱子的外边界；
• 每根柱子内部的所有分割边界（等分线）。

请输出画完整堵墙所需的最少线段数。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^5$）。

第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 10^9$）。

第三行包含 $n$ 个整数 $b_i$（$1 \le b_i \le 10^9$）。

输出格式

输出一行，包含一个整数，表示最少需要的线段数。

3
4 6 4
2 3 4

10

3
4 6 3
3 3 2

12

提示

【样例解释】

样例 #2 解释：如图，Hrvoje 会把第 $1$ 根柱子最上方的一条线段延伸到第 $2$ 根柱子，从而把两条线段“合并”为一条；他也会对墙底部的 $3$ 条线段做同样处理。最终总共画 $12$ 条线段，并且可以证明这是最小值。

【子任务】

子任务	分值	限制
$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$，且对每个 $i$，$b_i$ 整除 $a_i$
$4$	$57$	无额外限制