在直线上有 $n$ 个不同的点，共有 $m$ 种颜色，其中 $m \le n$。令 $S$ 为这些点的集合。我们希望选择一个非空子集 $C \subseteq S$，满足以下条件：

对于 $S - C$ 中的每一个点 $p$，在 $C$ 中的点里，距离 $p$ 最近的点必须与 $p$ 具有相同的颜色。当然，如果 $p$ 在 $C$ 中有多个距离最近的点，只要其中至少有一个点的颜色与 $p$ 相同即可。

例如，图 G.1 中有六个点，标记为 1 到 6，共有两种颜色。点 4 和点 5 是红色，其余为蓝色。集合 $\{2, 4, 6\}$ 满足上述性质。但集合 $\{2, 4\}$ 不满足该性质，因为点 6 在 $\{2, 4\}$ 中距离最近的点是点 4，而点 4 的颜色与点 6 不同。事实上，集合 $\{2, 4, 6\}$ 是满足该性质的最小基数子集。

图 G.1：直线上的六个彩色点

给定直线上的 $n$ 个不同点及其颜色，编写一个程序，找到一个满足上述性质且基数最小的非空子集 $C \subseteq S$，并输出该最小基数。

输入格式

程序从标准输入读取数据。输入的第一行包含两个整数 $m$ 和 $n$ ($1 \le m \le n \le 100,000$)，其中 $m$ 是颜色数量，$n$ 是点数。点从左到右依次编号为 1 到 $n$，颜色编号为 1 到 $m$。第二行包含一个由 $n$ 个递增整数组成的序列，其中第 $i$ 个数是点 $i$ 的坐标。点的坐标 $x$ 满足 $0 \le x \le 10^9$ 且互不相同。第三行包含一个由 $n$ 个整数组成的序列，其中第 $i$ 个数是点 $i$ 的颜色，颜色值在 1 到 $m$ 之间。

输出格式

程序将结果写入标准输出。仅输出一行，包含满足上述性质的非空子集 $C \subseteq S$ 的最小基数。

样例

样例输入 1

2 6
0 3 4 7 8 11
1 1 1 2 2 1

样例输出 1

3

样例输入 2

2 6
0 3 4 7 8 11
1 2 1 2 2 1

样例输出 2

5