0271 - 城壁 (Rampart)

問題

　歴史学者である JOI 教授は，かつて存在した IOI 王国について研究している．
過去の調査によると，IOI 王国は縦 H 行，横 W 列のマスに区切られた長方形の形をしていた．IOI 王国の首都は，防衛のために城壁で囲われていた．
　IOI 王国の首都を囲う城壁は次のような形をしている．城壁には大きさと呼ばれる値が定まっている．大きさ s (s ≥ 3) の城壁とは，s × s の正方形の領域から外周以外の (s - 2) × (s - 2) の正方形の領域を除いたものである．
　調査によると，首都を囲う城壁の大きさは L 以上であった．また，IOI 王国のいくつかのマスには城壁が存在しなかったことがわかっている．
　JOI 教授は，さらなる研究のために，城壁としてありうるものが何通りあるかを知りたい．

課題

　IOI 王国の大きさと，城壁の大きさの最小値，城壁が存在しなかったことが分かっているマスの情報が与えられたとき，城壁としてありうるものは何通りあるかを求めるプログラムを作成せよ．

入力

　標準入力から以下のデータを読み込め．

• 1 行目には，整数 H, W, L, P が空白を区切りとして書かれている．これは，IOI 王国は縦 H 行，横 W 列のマスに区切られた長方形の形をしており，城壁の大きさは L 以上であり，城壁が存在しなかったことがわかっているマスが P マス存在することを表す．
• 続く P 行のうちの i 行目 (1 ≤ i ≤ P) には，整数 A_i, B_i が空白を区切りとして書かれている．これは，IOI 王国の上から A_i 行目，左から B_i 列目のマスには城壁が存在しなかったことがわかっていることを表す．

出力

　標準出力に，城壁としてありうるものは何通りあるかを表す整数を 1 行で出力せよ．

制限

　すべての入力データは以下の条件を満たす．

• 1 ≤ H ≤ 4 000．
• 1 ≤ W ≤ 4 000．
• 3 ≤ L ≤ H かつ 3 ≤ L ≤ W．
• 0 ≤ P ≤ 100 000．
• 1 ≤ A_i ≤ H (1 ≤ i ≤ P)．
• 1 ≤ B_i ≤ W (1 ≤ i ≤ P)．
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ P)．

小課題

小課題 1 [4 点]

　以下の条件を満たす．

• H ≤ 500．
• W ≤ 500．

小課題 2 [16 点]

• 0 ≤ P ≤ 10 を満たす．

小課題 3 [80 点]

　追加の制限はない．

入出力例

入力例 1

5 5 3 2
2 2
4 3

出力例 1

4

この入力例の場合，城壁としてありうるものは以下の 4 通りが考えられる．ただし，× で示したマスは城壁が存在しなかったことがわかっているマスである．

入力例 2

7 8 4 3
2 2
3 7
6 5

出力例 2

13

入力例 3

4000 4000 1234 4
1161 3028
596 1892
3731 2606
702 1530

出力例 3

7050792912