Chain Explosion

Interview

Time limit8sMemory limit512 MB

Summary

Starting from one bomb, count how many bombs explode when each explosion detonates bombs up to D cells away along its row and column, chaining until nothing new detonates.

Level: Medium4 of 10
Topics: Graph, BFS, Simulation, Implementation
Solved: No attempts yet

Problem

You are playing a game that uses bombs. The field in this game is a grid with W columns and H rows. The cell in column x from the left and row y from the top is written as (x, y).

N bombs are placed on this field, and the position of the i-th bomb is (xi, yi). When a bomb in this game explodes, it detonates every bomb inside the cross-shaped region extending up to D cells in each of the four directions from the cell containing the bomb, and those bombs disappear. A bomb also explodes in a chain when it is detonated by another bomb. The explosions continue until no bomb remains that can explode.

To beat this game, it is important to know how many bombs explode in total when a given bomb is set off. You decide to write a program that helps you play the game well.

As an example, the last data set of the sample input is shown in the figures below. In this data set, the 4th bomb at position (4, 1) explodes first. After that, the explosions chain as follows.

The bomb at (4, 1) detonates every bomb within 3 cells in each of the four directions.
The bombs at (5, 1) and (4, 4) explode in the chain and detonate every bomb within 3 cells in each of their four directions.
The bombs at (3, 4) and (1, 4) explode in the chain. No new bombs are detonated at this point.

Therefore, when the bomb at (4, 1) explodes, 5 bombs explode in total.

Input

The input consists of at most 50 data sets. Each data set is given in the following format.

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

Each data set consists of N+1 lines.

Line 1 contains integers representing the width W (1 ≤ W ≤ 100) of the field, the height H (1 ≤ H ≤ 100), the number of bombs N (1 ≤ N ≤ min(100, WH)), the explosion size D (1 ≤ D ≤ 100), and the number B (1 ≤ B ≤ N) of the bomb that explodes first.

The N lines starting from line 2 give the positions of the N bombs. Line i + 1 contains integers representing the position (xi, yi) of the i-th bomb, with 1 ≤ xi ≤ W and 1 ≤ yi ≤ H. No two bombs in a data set are placed in the same cell.

The end of the input is marked by a line of five zeros.

Output

For each data set, print the number of bombs that end up exploding when the B-th bomb explodes first, on one line.

Examples1

Example 1

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

Expected output