007 - 積み荷の配置

問題

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

課題

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

入力

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

H N
x1 y1
x2 y2
:
xN yN

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

出力

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

入出力例

入力例1

5 3
0 1
1 2
3 3

出力例1

2

入力例2

6 4
0 2
1 3
3 4
0 5

出力例2

4