P14781 [COCI 2025/2026 #3] 尺子 / Ravnalo

本题满分 $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$）。

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

#### 【样例解释】 样例 #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$ | 无额外限制 |