P11335 [NOISG 2020 Finals] Arcade

Emily 是一只外星章鱼，她正在玩一个街机游戏。

游戏机上有 $N$ 个按钮，从左到右编号为 $1$ 到 $N$。游戏的规则是按照时间顺序按下 $M$ 个按钮，每秒按一个按钮。在第 $T_i$ 秒时，需要按下按钮 $A_i$。注意，可能存在 $T_i = T_j$ 且 $A_i = A_j$，即使 $i \neq j$。 Emily 的每只手可以从任意位置开始游戏，每只手从一个按钮移动到相邻按钮需要正好 $1$ 秒的时间。Emily 的手可以同时移动，按下按钮所需时间为 $0$ 秒。由于外星章鱼拥有无限数量的手，她总是可以获得游戏的最高分。然而，由于 Emily 很懒，她不想使用太多的手。让我们计算完成游戏所需的最少手数 $S$。 你的任务是帮助 Emily 计算完成游戏所需的最少手数 $S$。

- 第一行包含两个整数 $N$ 和 $M$，分别表示按钮数量和按键次数。 - 第二行包含 $M$ 个整数，第 $i$ 个整数表示第 $T_i$ 秒。 - 第三行包含 $M$ 个整数，第 $i$ 个整数表示需要按下的按钮编号 $A_i$。

- 输出一个整数，表示完成游戏所需的最少手数。

【样例解释】 对于样例 #1： - 游戏开始时，Emily 的右手在按钮 $3$，左手在按钮 $1$。 - 接下来的一秒中，右手移动到按钮 $4$，左手按下按钮 $1$。 - 随后，右手和左手同时移动到按钮 $2$，并分别按下按钮。 - 最后，右手移动到按钮 $6$ 并按下。 - 总共需要 $2$ 只手完成任务，因此输出为 $2$。 【数据范围】 - $1 \leq N \leq 10^9$ - $1 \leq M \leq 5 \times 10^5$ - $1 \leq A_i \leq N$ - $1 \leq T_i \leq 10^9$ | 子任务编号 | 分值 | 限制条件 | |:---:|:---:|:---:| | $1$ | $7$ | $1 \leq N, M, T_i \leq 100$, $1 \leq S \leq 2$ | | $2$ | $11$ | $1 \leq N, M, T_i \leq 100$, $1 \leq S \leq 3$ | | $3$ | $12$ | $1 \leq N, M, T_i \leq 100$, $1 \leq S \leq 4$ | | $4$ | $21$ | $1 \leq M \leq 300$ | | $5$ | $14$ | $1 \leq M \leq 15,000$ | | $6$ | $20$ | $1 \leq M \leq 100,000$ | | $7$ | $15$ | 无额外限制 |