{"problem":{"name":"Defect-free Squares","description":{"content":"There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left of the grid.   Each square of the grid is holed or not. T","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc311_e"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $H$ rows and $W$ columns. Let $(i, j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left of the grid.  \nEach square of the grid is holed or not. There are exactly $N$ holed squares: $(a_1, b_1), (a_2, b_2), \\dots, (a_N, b_N)$.\nWhen the triple of positive integers $(i, j, n)$ satisfies the following condition, the square region whose top-left corner is $(i, j)$ and whose bottom-right corner is $(i + n - 1, j + n - 1)$ is called a **holeless square**.\n\n*   $i + n - 1 \\leq H$.\n*   $j + n - 1 \\leq W$.\n*   For every pair of non-negative integers $(k, l)$ such that $0 \\leq k \\leq n - 1, 0 \\leq l \\leq n - 1$, square $(i + k, j + l)$ is not holed.\n\nHow many holeless squares are in the grid?\n\n## Constraints\n\n*   $1 \\leq H, W \\leq 3000$\n*   $0 \\leq N \\leq \\min(H \\times W, 10^5)$\n*   $1 \\leq a_i \\leq H$\n*   $1 \\leq b_i \\leq W$\n*   All $(a_i, b_i)$ are pairwise different.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$H$ $W$ $N$\n$a_1$ $b_1$\n$a_2$ $b_2$\n$\\vdots$\n$a_N$ $b_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc311_e","tags":[],"sample_group":[["2 3 1\n2 3","6\n\nThere are six holeless squares, listed below. For the first five, $n = 1$, and the top-left and bottom-right corners are the same square.\n\n*   The square region whose top-left and bottom-right corners are $(1, 1)$.\n*   The square region whose top-left and bottom-right corners are $(1, 2)$.\n*   The square region whose top-left and bottom-right corners are $(1, 3)$.\n*   The square region whose top-left and bottom-right corners are $(2, 1)$.\n*   The square region whose top-left and bottom-right corners are $(2, 2)$.\n*   The square region whose top-left corner is $(1, 1)$ and whose bottom-right corner is $(2, 2)$."],["3 2 6\n1 1\n1 2\n2 1\n2 2\n3 1\n3 2","0\n\nThere may be no holeless square."],["1 1 0","1\n\nThe whole grid may be a holeless square."],["3000 3000 0","9004500500"]],"created_at":"2026-03-03 11:01:14"}}