Farm

There is a farm that borders a straight road. Suppose the road is on the $x$-axis. Each boundary edge of the farm field is either horizontal or vertical. The leftmost and the rightmost edges are vertical and adjacent to the base edge which lies on the road. The length of the base edge is equal to the sum of the lengths of all other horizontal edges. See Figure C.1 (a).

(a)	(b)

Figure C.1. A farm field and the pest infestation locations.

In Figure C.1, the dots on the boundary or in the interior of the farm field are the locations where pests have infested. To eradicate the infestation, a farmer divides the infested area into several rectangular areas that satisfy the following conditions.

• Each rectangular area must be contained within the farm. The edges of a rectangle may overlap the boundary of the farm.
• Each edge of a rectangular area is either horizontal or vertical.
• Rectangular areas are completely separated from each other, including their boundaries.
• Each pest infestation location must be contained within one of the rectangular areas. A pest infestation location may lie on an edge of a rectangle.

Figure C.1 (b) shows four rectangular areas covering all pest infestation locations. The farmer wants to minimize the number of rectangular areas.

Given the boundary of a farm and the pest infestation locations, compute the minimum number of rectangular areas that satisfy the above conditions.

The input starts with a line containing two integers, $m$ ($4 \le m \le 100\,000$) and $n$ ($0 \le n \le 100\,000$), where $m$ is the number of edges of the farm field and $n$ is the number of pest infestation locations.

The second line contains $m$ integers $v_1, v_2, \cdots, v_m$ ($v_1 = v_m = 0$, $0 \le v_i \le 10^6$). These are the $x$-coordinates of the vertical edges and the $y$-coordinates of the horizontal edges. They alternate when traversing the upper boundary of the farm field clockwise from the left end of the base edge to the right end.

Each of the following $n$ lines contains two integers $x$ and $y$, the coordinate $(x, y)$ of a pest infestation location. All locations lie on the boundary or in the interior of the farm field.

Print exactly one line containing an integer, the minimum number of rectangular areas that satisfy the conditions.