007 - 積み荷の配置

時間制限 1 秒 / メモリ制限 64 MB / 得点 11 / x 1 /


TLE
1sec
MLE
64MB
得点
11

問題

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

課題

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

入力

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

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

出力

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

入出力例

入力例1

5 3
0 1
1 2
3 3
出力例1
2


入力例2

6 4
0 2
1 3
3 4
0 5
出力例2
4