AT_gigacode_2019_f クローゼットの配置

[problemUrl]: https://atcoder.jp/contests/gigacode-2019/tasks/gigacode_2019_f ギガコード君は家を買いました．この家は，左右に $ H $ 分割，前後に $ W $ 分割された合計 $ H\ \times\ W $ 個の区画に分かれています．そのうち左から $ i $ 番目，前から $ j $ 番目のマスを $ (i,\ j) $ で表します． そのうち $ N $ 個の区画には物が置かれています．$ i $ 個目の物は，区画 $ (r_i,\ c_i) $ 全体を占めています．また，これらの物が動くことはありません． ギガコード君は，この家にクローゼットを $ 1 $ つ設置することにしました．クローゼットは家の外壁に平行な長方形でなければならず，クローゼットのある区画に物が置かれていてはなりません．しかし，地震が起きた時にクローゼットが動くと良くないので，次の条件を満たす置き方のうち $ 1 $ つを選ぶことにしました． - クローゼットを向きを変えずにどんな方向に動かそうとしても，物や家の外壁に当たって動かせない． 例えば，次のようなクローゼットの配置ができます．  しかし，条件を満たさないクローゼットの配置はできません．  条件を満たすようなクローゼットの配置はいくつあるか求めてください．

入力は以下の形式で標準入力から与えられます． > $ H $ $ W $ $ N $ $ r_1 $ $ c_1 $ $ r_2 $ $ c_2 $ : : $ r_N $ $ c_N $

地震が起きても動かないようなクローゼットの配置の数を出力してください．

### 制約 - $ 1\ \leq\ H\ \leq\ 5\ 000 $ - $ 1\ \leq\ W\ \leq\ 5\ 000 $ - $ 0\ \leq\ N\ \leq\ 201\ 900 $ - $ 1\ \leq\ r_i\ \leq\ H $ - $ 1\ \leq\ c_i\ \leq\ W $ - $ N $ 個の物はすべて異なる区画に置かれている - 入力はすべて整数 ### 部分点 この問題はいくつかの小課題に分けられ，その小課題のすべてのテストケースに正解した場合に「この小課題に正解した」とみなされます． 提出したソースコードの得点は，正解した小課題の点数の合計となります． 1. (2 点) $ H\ =\ 1,\ W\ =\ 1 $ 2. (11 点) $ H\ =\ 1,\ W\ \leq\ 25 $ 3. (11 点) $ H\ \leq\ 25,\ W\ \leq\ 25 $ 4. (19 点) $ N\ \leq\ 10 $ 5. (16 点) $ H\ \leq\ 100,\ W\ \leq\ 100 $ 6. (17 点) $ H\ \leq\ 350,\ W\ \leq\ 350 $ 7. (19 点) $ H\ \leq\ 1500,\ W\ \leq\ 1500 $ 8. (5 点) 追加の制約はない． ### 注意 **入力のサイズが大きいので、高速な入出力（C++ の場合 scanf/printf など）を使うことが推奨されています．**