AT_abc413_f [ABC413F] No Passage

There is an $ H \times W $ grid. Let $ (i,j) $ denote the cell at the $ i $ -th row from the top and $ j $ -th column from the left. Among these, $ K $ cells are goals. The $ i $ -th goal $ (1 \leq i \leq K) $ is cell $ (R_i, C_i) $ . Takahashi and Aoki play a game using this grid and a single piece placed on the grid. Takahashi and Aoki repeatedly perform the following series of operations until the piece reaches a goal cell: - Aoki chooses an integer $ a $ between $ 1 $ and $ 4 $ , inclusive. - Then, Takahashi chooses an integer $ b $ between $ 1 $ and $ 4 $ , inclusive, where $ a \neq b $ must be satisfied. Let $ (i,j) $ be the cell where the piece is placed before the operation. Based on the chosen integer $ b $ and the piece's position, move the piece. - When $ b=1 $ : If $ (i-1,j) $ is within the grid, move the piece from cell $ (i,j) $ to cell $ (i-1,j) $ ; if it is outside the grid, do nothing. - When $ b=2 $ : If $ (i+1,j) $ is within the grid, move the piece from cell $ (i,j) $ to cell $ (i+1,j) $ ; if it is outside the grid, do nothing. - When $ b=3 $ : If $ (i,j-1) $ is within the grid, move the piece from cell $ (i,j) $ to cell $ (i,j-1) $ ; if it is outside the grid, do nothing. - When $ b=4 $ : If $ (i,j+1) $ is within the grid, move the piece from cell $ (i,j) $ to cell $ (i,j+1) $ ; if it is outside the grid, do nothing. Takahashi's objective is to minimize the number of moves until the piece reaches a goal. Aoki's objective is to prevent the piece from reaching the goal; if that is impossible, his objective is to maximize the number of moves until the piece reaches a goal. For all pairs of integers $ (i,j) $ satisfying $ 1 \leq i \leq H,1 \leq j \leq W $ , solve the following problem and find the sum of all solutions: > Start the game with the piece at cell $ (i,j) $ . Assume both players act optimally toward their respective objectives. If Takahashi can make the piece reach a goal, the solution is the minimum number of moves; otherwise, the solution is $ 0 $ .

The input is given from standard input in the following format: > $ H $ $ W $ $ K $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_K $ $ C_K $

Print the answer.

### Sample Explanation 1 When $ (i,j)=(1,2),(2,1) $ , the starting cell is a goal, so the solution is $ 0 $ . When $ (i,j)=(1,1),(2,2) $ , no matter which $ a $ Aoki chooses, Takahashi can make the piece reach a goal in $ 1 $ move from the starting cell, so the solution is $ 1 $ . When $ (i,j)=(1,3),(2,3) $ , Takahashi cannot reach a goal, so the solution is $ 0 $ . The sum of these is $ 0 \times 2 + 1 \times 2 + 0 \times 2 = 2 $ . Thus, print $ 2 $ . ### Constraints - $ 2 \leq H \leq 3000 $ - $ 2 \leq W \leq 3000 $ - $ 1 \leq K \leq \min(HW,3000) $ - $ 1 \leq R_i \leq H $ - $ 1 \leq C_i \leq W $ - $ (R_i,C_i) \neq (R_j,C_j) $ ( $ 1 \leq i < j \leq K $ ) - All input values are integers.