AT_abc413_f [ABC413F] No Passage

$ H $ 行 $ W $ 列のグリッドがあります。上から $ i $ 行目、左から $ j $ 列目のマスを $ (i,j) $ と表します。また、このうち $ K $ 個のマスはゴールになっています。 $ i $ 個目 $ (1 \leq i \leq K) $ のゴールはマス $ (R_i, C_i) $ です。 高橋君と青木君はこのグリッドとグリッドの上に置かれた $ 1 $ つのコマを使ってあるゲームをしています。高橋君と青木君はコマがゴールのマスに到達するまで以下の一連の操作を繰り返し行います。 - 青木君は $ 1 $ 以上 $ 4 $ 以下の整数 $ a $ を選ぶ。 - その後、高橋君は $ 1 $ 以上 $ 4 $ 以下の整数 $ b $ を選ぶ。ただし、 $ a \neq b $ を満たす必要がある。操作前にコマが置いてあるマスを $ (i,j) $ としたとき、選んだ整数 $ b $ とコマの位置に応じて以下の通りにコマを移動させる。 - $ b=1 $ のとき: マス $ (i-1,j) $ がグリッド内である場合はコマをマス $ (i,j) $ からマス $ (i-1,j) $ に移動させ、グリッドの外である場合はコマを移動させない。 - $ b=2 $ のとき: マス $ (i+1,j) $ がグリッド内である場合はコマをマス $ (i,j) $ からマス $ (i+1,j) $ に移動させ、グリッドの外である場合はコマを移動させない。 - $ b=3 $ のとき: マス $ (i,j-1) $ がグリッド内である場合はコマをマス $ (i,j) $ からマス $ (i,j-1) $ に移動させ、グリッドの外である場合はコマを移動させない。 - $ b=4 $ のとき: マス $ (i,j+1) $ がグリッド内である場合はコマをマス $ (i,j) $ からマス $ (i,j+1) $ に移動させ、グリッドの外である場合はコマを移動させない。 高橋君の目的はコマがゴールに到達するまでの移動回数を最小化することです。青木君の目的はコマがゴールに到達しないようにすることであり、それが不可能な場合は移動回数を最大化することです。 $ 1 \leq i \leq H,1 \leq j \leq W $ を満たすすべての整数の組 $ (i,j) $ に対して以下の問題を解き、解の総和を求めてください。 > コマがマス $ (i,j) $ にある状態からゲームを始める。両者が各々の目的を目指して最適に行動するとき、高橋君がコマをゴールに到達させることができるのであれば移動回数の最小値、そうでないならば $ 0 $ が解である。

入力は以下の形式で標準入力から与えられる。 > $ H $ $ W $ $ K $ $ R_1 $ $ C_1 $ $ R_2 $ $ C_2 $ $ \vdots $ $ R_K $ $ C_K $

答えを出力せよ。

### Sample Explanation 1 $ (i,j)=(1,2),(2,1) $ のとき、開始するマスがゴールであるため、解は $ 0 $ です。 $ (i,j)=(1,1),(2,2) $ のとき、どの $ a $ を青木君が選んでも高橋君は $ 1 $ 回の移動でコマをゴールに到達させることができるため、解は $ 1 $ です。 $ (i,j)=(1,3),(2,3) $ のとき、高橋君はコマをゴールに到達させることができないため、解は $ 0 $ です。 これらの合計は $ 0 \times 2 + 1 \times 2 + 0 \times 2 = 2 $ です。よって $ 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 $ ) - 入力はすべて整数