Problem Statement

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

部屋は正方形のマスが縦に $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$ 個になるようにしたいです。このような移動先として考えられるマスの総数を求めてください。

Input

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

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$ 点が与えられる。

Output

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