AT_abc436_c [ABC436C] 2x2 Placing

$ N $ 行 $ N $ 列のマス目があります。 上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表記します。 はじめ、マス目の上には何も置かれていません。 今から $ M $ 回の操作を行います。 $ i $ 回目 $ (1\leq i\leq M) $ の操作は以下の通りです。 - マス $ (R_i,C_i) $ を左上とする $ 2 \times 2 $ の領域を占めるブロックを、既に置かれている他のブロックと位置が重ならない場合、またその場合に限り、マス目の上に置く。 より厳密には、マス集合 $ S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace $ に対し、既にマス目の上に置かれているブロックであって $ S $ に含まれるいずれかのマスを占めるものが存在するならば何も行わず、 存在しないならば $ S $ に含まれる $ 4 $ マス全体を占めるブロックを置く。 全ての操作を行った後、マス目の上に何個のブロックが置かれているか求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_M $ $ C_M $

答えを出力せよ。

### Sample Explanation 1 以下の図は操作のようすを示したものであり、黒く塗られた領域がブロックを、赤枠で囲まれた領域が次にブロックを置きたい場所を表しています。  - $ 1 $ 回目の操作：マス $ (1,1) $ を左上とする $ 2 \times 2 $ の領域には何も置かれていないため、そこにブロックを置きます。 - $ 2 $ 回目の操作：マス $ (2,2) $ を左上とする $ 2 \times 2 $ の領域のうち、マス $ (2,2) $ 上に既に他のブロックが存在するため、何も行いません。 - $ 3 $ 回目の操作：マス $ (2,3) $ を左上とする $ 2 \times 2 $ の領域には何も置かれていないため、そこにブロックを置きます。 よって、全ての操作を行った後、マス目の上に $ 2 $ 個のブロックが置かれています。 ### Sample Explanation 2 全ての操作においてブロックを置くことができます。 ### Sample Explanation 3 $ (R_i,C_i)=(R_j,C_j) $ を満たす $ i,j\ (i\neq j) $ が存在することもあります。 ### Constraints - $ 2\leq N \leq 10^9 $ - $ 1\leq M \leq 2\times 10^5 $ - $ 1\leq R_i,C_i \leq N-1 $ - 入力は全て整数