AtCoder Beginner Contest 023

C - 収集王


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

高橋君はある部屋に移動する予定です。

部屋は正方形のマスが縦に R 行、横に C 列並んだ形状をしています。このうち i (1 ≦ i ≦ R) 行目の j (1 ≦ j ≦ C) 列目にあるマスをマス (i,j) と呼ぶことにします。

これらのマスには飴が合計 N 個存在します。飴には 1 から N までの番号が付けられており、飴 i (1 ≦ i ≦ N) はマス (r_i,c_i) に置いてあります。これらのうちどの 2 つの飴も同一のマス上にありません。

高橋君はマスのうち任意の 1 マスに移動します。移動した後、高橋君は次に示すように飴を獲得します。

  • 最初に、高橋君がいるマスと同じ行にあるすべてのマスについて、そのマスにある飴をすべて獲得する。
  • 次に、高橋君がいるマスと同じ列にあるすべてのマスについて、そのマスにあるすべての飴を獲得する。

高橋君はこの行動以外には何も行動しません。

高橋君は獲得する飴の個数がちょうど K 個になるようにしたいです。このような移動先として考えられるマスの総数を求めてください。


入力

入力は以下の形式で標準入力から与えられる。

R C K
N
r_1 c_1
r_2 c_2
:
r_N c_N
  • 1 行目には、3 つの整数 R (1 ≦ R ≦ 100,000), C (1 ≦ C ≦ 100,000), K (1 ≦ K ≦ 100,000) が空白区切りで書かれている。これは、部屋を構成する正方形マスが縦 R 行、横 C 列あることを表す。K は高橋君が獲得したい飴の個数である。
  • 2 行目には、飴の個数を表す整数 N (K ≦ N ≦ 100,000) が与えられる。
  • 3 行目から N 行には、飴に関する情報が与えられる。N 行のうち i (1 ≦ i ≦ N) 行目には、2 つの整数 r_i (1 ≦ r_i ≦ R), c_i (1 ≦ c_i ≦ C) が空白区切りで書かれている。これは飴 i がマス (r_i,c_i) にあることを表す。
  • i≠j のとき、(r_i,c_i)≠(r_j,c_j) となる。

部分点

この問題には部分点が設定されている。

  • R ≦ 50 かつ C ≦ 50 かつ N ≦ 50 を満たすデータセット 1 に正解した場合は、30 点が与えられる。
  • 追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

獲得する飴の個数がちょうど K 個になるような移動先の総数を 1 行に出力せよ。出力の末尾にも改行を入れること。


入力例1

3 5 3
5
1 2
2 1
2 5
3 2
3 5

出力例1

5

例えば、マス (3,2) に高橋君が移動した場合を考えます。

  • 1 は、マス (1,2) にあります。このマスはマス (3,2) と同じ列にあるので、高橋君は飴 1 を獲得します。
  • 2 は、マス (2,1) にあります。このマスはマス (3,2) と同じ行にも同じ列にもないので、高橋君は飴 2 を獲得しません。
  • 3 は、マス (2,5) にあります。このマスはマス (3,2) と同じ行にも同じ列にもないので、高橋君は飴 3 を獲得しません。
  • 4 は、マス (3,2) にあります。このマスはマス (3,2) と同じマス (同じ行かつ同じ列) にあるので、高橋君は飴 4 を獲得します。
  • 5 は、マス (3,5) にあります。このマスはマス (3,2) と同じ行にあるので、高橋君は飴 5 を獲得します。

以上より、飴 1, 4, 5 のちょうど 3 個だけ飴を獲得するので、マス (3,2) は獲得する飴の個数がちょうど K 個になるような移動先です。

他にもマス (1,5), (2,5), (3,1), (3,5) が条件をみたすので答えとして 5 を出力します。


入力例2

7 3 1
4
3 2
3 3
4 2
4 3

出力例2

0

どのように移動先を指定しても、獲得する飴の個数をちょうど 1 個にすることはできません。


入力例3

5 5 2
5
1 1
2 2
3 3
4 4
5 5

出力例3

20

Submit提出する