005 - 爆発の連鎖

時間制限 8 秒 / メモリ制限 256 MB / 得点 20 / x 15 /


TLE
8sec
MLE
256MB
得点
20

問題

あなたは爆弾を使ったゲームで遊んでいる.このゲームのフィールドは幅 W マス,高さ H マスのマス目状である.このフィールドの左から x 列目,上から y 行目のマスは (x, y) と表される.

このフィールド上に N 個の爆弾が配置されており,i 番目の爆弾の位置は (xi, yi) である.このゲームの爆弾は,爆発したとき爆弾のあるマスから上下左右それぞれの方向 D マス以内の十字型の領域内にある爆弾を誘爆して消失する.また,爆弾は別の爆弾によって誘爆されたときにも連鎖して爆発する.この爆発は他に爆発する爆弾が無くなるまで続く.

このゲームの攻略には,ある爆弾を爆発させたときに合計で何個の爆弾が爆発するか知ることが重要である.あなたは攻略を有利に進めるためのプログラムを作ることにした.

例として,入力サンプルの最後のデータセットは以下の図のようになる.このデータセットでは (4, 1) の位置にある 4 番目の爆弾が最初に爆発する.その後,以下のように爆発が連鎖する.

  • (4, 1) の位置の爆弾から上下左右それぞれの方向 3 マス以内にある爆弾を誘爆する.
  • (5, 1)(4, 4) の位置の爆弾が誘爆により連鎖して爆発し,各々の上下左右それぞれの方向 3 マス以内にある爆弾を誘爆する.
  • (3, 4)(1, 4) の位置の爆弾が誘爆により連鎖して爆発する.このとき新しく誘爆される爆弾はない.

よって (4, 1) の位置にある爆弾が爆発すると合計で 5 つの爆弾が爆発する.

Input

入力は最大で 50 個のデータセットからなる.各データセットは次の形式で表される.

W H N D B x1 y1 x2 y2 ... xN yN

各データセットは N+1 行からなる.

1 行目はフィールドの幅 W (1 ≤ W ≤ 100),高さ H (1 ≤ H ≤ 100),爆弾の数 N (1 ≤ N ≤ min(100, WH)),爆弾の爆発の大きさ D (1 ≤ D ≤ 100),最初に爆発する爆弾の番号 B (1 ≤ B ≤ N) を表す整数である.

2 行目から続く N 行はそれぞれ N 個の爆弾の位置を表す.i + 1 行目は i 番目の爆弾の位置 (xi, yi) を表す整数であり 1 ≤ xi ≤ W1 ≤ yi ≤ H を満たす.各データセットについて同じマスに複数の爆弾が配置されることはない.

入力の終わりは 5 つのゼロからなる行で表される.

Output

各データセットについて,最初に B 番目の爆弾が爆発したときに,最終的に爆発する爆弾の数を 1 行で出力せよ.

Sample Input

10 5 5 3 1
1 5
2 5
5 5
5 4
10 5
50 50 1 100 1
25 25
1 100 7 10 4
1 5
1 10
1 40
1 50
1 55
1 63
1 74
3 3 5 3 5
1 1
1 3
3 1
3 3
2 2
20 20 10 10 1
5 5
20 5
5 10
20 8
5 20
10 10
17 17
11 10
8 9
11 20
5 5 7 3 4
1 4
2 2
3 4
4 1
4 4
5 1
5 5
0 0 0 0 0

Output for the Sample Input

4
1
4
1
6
5