AT_abc436_c [ABC436C] 2x2 Placing

There is a grid with $ N $ rows and $ N $ columns. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. Initially, nothing is placed on the grid. You will now perform $ M $ operations. The $ i $ -th operation $ (1\leq i\leq M) $ is as follows: - Place a block that occupies a $ 2 \times 2 $ region with cell $ (R_i,C_i) $ as the top-left corner on the grid if and only if its position does not overlap with any other blocks already placed. More precisely, for the set of cells $ S=\lbrace (R_i,C_i),(R_i+1,C_i),(R_i,C_i+1),(R_i+1,C_i+1)\rbrace $ , if there exists a block already placed on the grid that occupies any cell in $ S $ , do nothing; otherwise, place a block that occupies all four cells in $ S $ . After performing all operations, find how many blocks are placed on the grid.

The input is given from Standard Input in the following format: > $ N $ $ M $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_M $ $ C_M $

Print the answer.

### Sample Explanation 1 The following diagram shows the operations, where black-filled regions represent blocks and red-framed regions represent where the next block is to be placed.  - Operation $ 1 $ : Nothing is placed in the $ 2 \times 2 $ region with cell $ (1,1) $ as the top-left corner, so place a block there. - Operation $ 2 $ : Among the $ 2 \times 2 $ region with cell $ (2,2) $ as the top-left corner, there is already another block on cell $ (2,2) $ , so do nothing. - Operation $ 3 $ : Nothing is placed in the $ 2 \times 2 $ region with cell $ (2,3) $ as the top-left corner, so place a block there. Thus, after performing all operations, two blocks are placed on the grid. ### Sample Explanation 2 Blocks can be placed in all operations. ### Sample Explanation 3 There may exist $ i,j\ (i\neq j) $ such that $ (R_i,C_i)=(R_j,C_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 $ - All input values are integers.