{"problem":{"name":"Rook on Grid","description":{"content":"We have a grid with $H$ horizontal rows and $W$ vertical columns. Let Square $(i,j)$ be the square at the $i$\\-th row and $j$\\-th column. There are $M$ obstacles on this grid. The $i$\\-th obstacle is ","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc186_f"},"statements":[{"statement_type":"Markdown","content":"We have a grid with $H$ horizontal rows and $W$ vertical columns. Let Square $(i,j)$ be the square at the $i$\\-th row and $j$\\-th column.\nThere are $M$ obstacles on this grid. The $i$\\-th obstacle is at Square $(X_i, Y_i)$.\nWe have a rook, the chess piece, on Square $(1, 1)$. In one move, it can move to the right or downward through any number of squares without obstacles.\nFind the number of squares the rook can reach in two moves or less.\n\n## Constraints\n\n*   $1\\leq H,W \\leq 2\\times 10^5$\n*   $0\\leq M \\leq 2\\times 10^5$\n*   $1\\leq X_i \\leq H$\n*   $1\\leq Y_i \\leq W$\n*   $(X_i,Y_i) \\neq (1,1)$\n*   $(X_i,Y_i)$ are distinct.\n*   All values in input are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $M$\n$X_1$ $Y_1$\n$\\vdots$\n$X_M$ $Y_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc186_f","tags":[],"sample_group":[["4 3 2\n2 2\n3 3","10\n\nEvery square without an obstacle can be reached in two moves or less."],["5 4 4\n3 2\n3 4\n4 2\n5 2","14\n\nEvery square without an obstacle except $(4,4)$ and $(5,4)$ can be reached in two moves or less."],["200000 200000 0","40000000000"]],"created_at":"2026-03-03 11:01:14"}}