Loading

Aizu Ocean Transport Company (AOTC) accepted a new shipping order. The pieces of the cargo included in this order all have the same square footprint (2m x 2m). The cargo room has a rectangular storage space of 4m width with various longitudinal extents. Each pieces of cargo must be placed in alignment with partition boundaries which form a 1m x 1m square grid. A straddling arrangement with a neighboring partition (for example, protrusion by 50 cm) is not allowed. Neither an angled layout nor stacked placement are allowed. Note also that there may be some partitions on which any cargo loading is prohibited.

AOTC wishes to use the currently available ship for this consignment and needs to know how many pieces of cargo it can accommodate.

Make a program to report the maximum cargo capacity of the cargo space given the following information: the depth (m) of the cargo space and the loading-inhibited partitions.

Input

The input is given in the following format.

H N
x_1 y_1
x_2 y_2
:
x_N y_N

The first line provides the longitudinal depth H (2 ≤ H ≤ 10⁴) of the cargo space in meters and the number of load-inhibited partitions N (0 ≤ N ≤ 4 × 10⁴). Each of the subsequent N lines defines the position of the i-th load-inhibited partition x_i (0 ≤ x_i ≤ 3) and y_i (0 ≤ y_i ≤ H-1) in integers, where x = 0 and y = 0 indicate the bottom-left corner partition. A load-inhibited partition appears only once in the list.

Output

Output the maximum number of cargo pieces loaded into the cargo space.

Sample Input 1

5 3
0 1
1 2
3 3

Sample Output 1

2

Input example 1 corresponds to the cargo layout shown in the left-most figure.

Sample Input 2

6 4
0 2
1 3
3 4
0 5

Sample Output 2

4