Loading

Time Limit : 1 sec, Memory Limit : 262144 KB

積み荷の配置

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



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

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

Input

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

H N
x_1 y_1
x_2 y_2
:
x_N y_N

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

Output

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

Sample Input 1

5 3
0 1
1 2
3 3

Sample Output 1

2

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

Sample Input 2

6 4
0 2
1 3
3 4
0 5

Sample Output 2

4

Source: PC Koshien 2017 , All-Japan High School Programming Contest, Aizu-Wakamatsu, Japan, 2017-9-9
http://web-ext.u-aizu.ac.jp/pc-concours/