有一个农场毗邻一条笔直的道路。假设这条道路位于 $x$ 轴上。农场田地的每一条边界边要么是水平的，要么是垂直的。最左侧和最右侧的边是垂直的，并与位于道路上的基边相邻。基边的长度等于所有其他水平边长度之和。参见图 C.1 (a)。

图 C.1. 农场田地及害虫侵扰位置

在图 C.1 中，边界上或农场田地内部的点代表害虫侵扰的位置。为了有效地根除这些侵扰，农民试图将受侵扰的区域划分为若干个满足以下条件的矩形区域：

• 每个矩形区域必须包含在农场内。矩形的边允许与农场的边界重合。
• 矩形区域的每一条边要么是水平的，要么是垂直的。
• 矩形区域之间必须完全分离，包括它们的边界。
• 每个害虫侵扰位置必须包含在一个矩形区域内。害虫侵扰位置允许位于矩形的边上。

图 C.1 (b) 展示了覆盖所有害虫侵扰位置的四个矩形区域。农民希望最小化矩形区域的数量，以便进行高效的害虫管理。

给定农场的边界和害虫侵扰位置，编写一个程序来计算满足上述条件的最小矩形区域数量。

输入格式

程序从标准输入读取数据。输入的第一行包含两个整数 $m$ ($4 \le m \le 100,000$) 和 $n$ ($0 \le n \le 100,000$)，其中 $m$ 是农场田地的边数，$n$ 是害虫侵扰位置的数量。第二行给出 $m$ 个整数 $v_1, v_2, \dots, v_m$ ($v_1 = v_m = 0, 0 \le v_i \le 10^6$)，它们代表垂直边的 $x$ 坐标和水平边的 $y$ 坐标。当从基边的左端点沿顺时针方向遍历农场田地的上边界时，会交替遇到这些垂直边和水平边。从第三行开始，每一行包含两个整数 $x$ 和 $y$，代表一个害虫侵扰位置的坐标 $(x, y)$。所有位置均位于农场田地的边界上或内部。

输出格式

程序将结果写入标准输出。仅打印一行，包含一个整数，表示满足上述条件的最小矩形区域数量。

样例

输入 1

12 8
0 30 20 20 30 40 40 10 50 20 70 0
4 5
15 26
25 15
35 15
35 35
50 5
55 15
60 20

输出 1

4

输入 2

4 0
0 10 50 0

输出 2

0

输入 3

12 3
0 3 2 6 4 1 6 4 8 2 10 0
3 5
7 3
3 1

输出 3

2