{"problem":{"name":"White Pawn","description":{"content":"Let $N$ be a positive integer. We have a $(2N+1)\\times (2N+1)$ grid where rows are numbered $0$ through $2N$ and columns are also numbered $0$ through $2N$. Let $(i,j)$ denote the square at Row $i$ an","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc203_e"},"statements":[{"statement_type":"Markdown","content":"Let $N$ be a positive integer. We have a $(2N+1)\\times (2N+1)$ grid where rows are numbered $0$ through $2N$ and columns are also numbered $0$ through $2N$. Let $(i,j)$ denote the square at Row $i$ and Column $j$.\nWe have one white pawn, which is initially at $(0, N)$. Also, we have $M$ black pawns, the $i$\\-th of which is at $(X_i, Y_i)$.\nWhen the white pawn is at $(i, j)$, you can do one of the following operations to move it:\n\n*   If $0\\leq i\\leq 2N-1$, $0 \\leq j\\leq 2N$ hold and $(i+1,j)$ **does not** contain a black pawn, move the white pawn to $(i+1, j)$.\n*   If $0\\leq i\\leq 2N-1$, $0 \\leq j\\leq 2N-1$ hold and $(i+1,j+1)$ **does** contain a black pawn, move the white pawn to $(i+1,j+1)$.\n*   If $0\\leq i\\leq 2N-1$, $1 \\leq j\\leq 2N$ hold and $(i+1,j-1)$ **does** contain a black pawn, move the white pawn to $(i+1,j-1)$.\n\nYou cannot move the black pawns.\nFind the number of integers $Y$ such that it is possible to have the white pawn at $(2N, Y)$ by repeating these operations.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10^9$\n*   $0 \\leq M \\leq 2\\times 10^5$\n*   $1 \\leq X_i \\leq 2N$\n*   $0 \\leq Y_i \\leq 2N$\n*   $(X_i, Y_i) \\neq (X_j, Y_j)$ $(i \\neq j)$\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $M$\n$X_1$ $Y_1$\n$:$\n$X_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc203_e","tags":[],"sample_group":[["2 4\n1 1\n1 2\n2 0\n4 2","3\n\nWe can move the white pawn to $(4,0)$, $(4,1)$, and $(4,2)$, as follows:\n\n*   $(0,2)\\to (1,1)\\to (2,1)\\to (3,1)\\to (4,2)$\n*   $(0,2)\\to (1,1)\\to (2,1)\\to (3,1)\\to (4,1)$\n*   $(0,2)\\to (1,1)\\to (2,0)\\to (3,0)\\to (4,0)$\n\nOn the other hand, we cannot move it to $(4,3)$ or $(4,4)$. Thus, we should print $3$."],["1 1\n1 1","0\n\nWe cannot move the white pawn from $(0,1)$."]],"created_at":"2026-03-03 11:01:14"}}