積み荷の配置

会津海上運送会社に、新たな積み荷の輸送依頼が舞い込んだ。今回依頼された荷物は、すべて同じ大きさで、横幅が２ｍ、縦幅が２ｍである。貨物室は長方形で、横幅が４ｍで固定されているが、縦幅はさまざまである。また、荷物は横と縦それぞれ１ｍを単位とした区画の境界に合わせて置く必要があり（５０ｃｍずらしたりなどはできない）、傾けて置いたり、重ねて置いたりすることはできない。また、荷物が置けない区画もある。

現在使える船の貨物室に荷物をできるだけ積んで輸送したいが、最大でいくつ積めるかを知りたい。

貨物室の縦の長さと、その中で荷物が置けない区画が与えられたとき、最大でいくつの荷物が積めるかを報告するプログラムを作成せよ。

Input

入力は以下の形式で与えられる。

H N
x_1 y_1
x_2 y_2
:
x_N y_N

１行目にメートル単位の貨物室の縦の長さ H (2 ≤ H ≤ 10⁴) と、荷物が置けない区画の数 N (0 ≤ N ≤ 4 × 10⁴) が与えられる。続く N 行に、荷物が置けない区画の位置が与えられる。x_i (0 ≤ x_i ≤ 3) と y_i (0 ≤ y_i ≤ H-1) はそれぞれ横方向と縦方向の値を表す整数である。ただし、左下隅の区画の位置を x = 0, y = 0 とする。同じ位置が２回以上現れることはない。

Output

最大でいくつの荷物が積めるかを１行に出力する。

Sample Input 1

5 3
0 1
1 2
3 3

Sample Output 1

2

入力例１は問題文中の左端の図の状態を表す。

Sample Input 2

6 4
0 2
1 3
3 4
0 5

Sample Output 2

4

Note

Algorithm

 

---