题目描述

译自 NOISG 2020 Final T4. Arcade

外星章鱼艾米丽正在玩一款街机游戏。游戏机包含 $N$ 个按钮，从左到右编号为 $1$ 到 $N$。游戏需要按顺序按下 $M$ 个按钮，每秒按一个。在游戏开始后的第 $T_i$ 秒，必须按下按钮 $A_i$。注意，即使 $i \neq j$，也可能有 $T_i = T_j$ 或 $A_i = A_j$。

艾米丽的每只手在游戏开始时可以位于任意位置，从一个按钮移动到旁边的按钮需要正好 $1$ 秒。艾米丽的双手可以同时移动，且按下按钮不需要时间。作为外星章鱼，艾米丽拥有无限多的手，因此总能通过完成所有 $M$ 次按钮按下来获得最高分。然而，艾米丽很懒，不想使用所有手。设获得最高分所需的最少手数为 $S$。

给定艾米丽需要完成的精确按钮按压序列，帮助她找出获得游戏最高分所需的最少手数。帮助艾米丽计算并提供 $S$ 的值。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $M$。

第二行包含 $M$ 个整数，其中第 $i$ 个整数表示 $T_i$。

第三行包含 $M$ 个整数，其中第 $i$ 个整数表示 $A_i$。

输出格式

程序需向标准输出输出结果。

输出一行，包含一个整数，表示艾米丽获得游戏最高分所需的最少手数。

6 4
1 2 3 4
3 1 2 6

2

在游戏开始时，艾米丽的双手位于以下位置，右手按下按钮 $3$：

在下一秒，艾米丽将右手向右移动一个按钮，并用左手按下按钮 $1$：

随后，她将双手同时向右移动一个按钮，并按下按钮 $2$：

在最后一秒，她将右手向右移动一步并按下按钮 $6$：

因此，艾米丽需要两只手完成游戏。$S$ 的值为 $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$

设获得最高分所需的最少手数为 $S$。详细子任务附加限制及分值如下表所示：