You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

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$。

输出格式

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

6 4
1 2 3 4
3 1 2 6

2

提示

【样例解释】

对于样例 #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$	无额外限制