{"problem":{"name":"Grid game","description":{"content":"Takahashi and Aoki will play a game using a grid with $H$ rows and $W$ columns of square cells. There are $N$ obstacles on this grid; the $i$\\-th obstacle is at $(X_i,Y_i)$. Here, we represent the cel","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc029_d"},"statements":[{"statement_type":"Markdown","content":"Takahashi and Aoki will play a game using a grid with $H$ rows and $W$ columns of square cells. There are $N$ obstacles on this grid; the $i$\\-th obstacle is at $(X_i,Y_i)$. Here, we represent the cell at the $i$\\-th row and $j$\\-th column $(1 \\leq i \\leq H, 1 \\leq j \\leq W)$ by $(i,j)$. There is no obstacle at $(1,1)$, and there is a piece placed there at $(1,1)$.\nStarting from Takahashi, he and Aoki alternately perform one of the following actions:\n\n*   Move the piece to an adjacent cell. Here, let the position of the piece be $(x,y)$. Then Takahashi can only move the piece to $(x+1,y)$, and Aoki can only move the piece to $(x,y+1)$. If the destination cell does not exist or it is occupied by an obstacle, this action cannot be taken.\n*   Do not move the piece, and end his turn without affecting the grid.\n\nThe game ends when the piece does not move twice in a row.\nTakahashi would like to perform as many actions (including not moving the piece) as possible before the game ends, while Aoki would like to perform as few actions as possible before the game ends. How many actions will Takahashi end up performing?\n\n## Constraints\n\n*   $1 \\leq H,W \\leq 2\\times 10^5$\n*   $0 \\leq N \\leq 2\\times 10^5$\n*   $1 \\leq X_i \\leq H$\n*   $1 \\leq Y_i \\leq W$\n*   If $i \\neq j$, $(X_i,Y_i) \\neq (X_j,Y_j)$\n*   $(X_i,Y_i) \\neq (1,1)$\n*   $X_i$ and $Y_i$ are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$H$ $W$ $N$\n$X_1$ $Y_1$\n$:$\n$X_N$ $Y_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc029_d","tags":[],"sample_group":[["3 3 1\n3 2","2\n\nFor example, the game proceeds as follows:\n\n*   Takahashi moves the piece to (2,1).\n*   Aoki does not move the piece.\n*   Takahashi moves the piece to (3,1).\n*   Aoki does not move the piece.\n*   Takahashi does not move the piece.\n\nTakahashi performs three actions in this case, but if both players play optimally, Takahashi will perform only two actions before the game ends."],["10 10 14\n4 3\n2 2\n7 3\n9 10\n7 7\n8 1\n10 10\n5 4\n3 4\n2 8\n6 4\n4 4\n5 8\n9 2","6"],["100000 100000 0","100000"]],"created_at":"2026-03-03 11:01:13"}}