|
F |
Winger
Trial |
|
After the great winger Donaldo left his soccer team, coach sir Thelex has found himself in a great fix. The strength of his team is reduced greatly and he needs to find a suitable replacement immediately. The coach selects a number of young wingers from around the world and sets up a trial for them.
The trial will take place on a rectangular shaped field of length L meters & width W meters. There are N robot defenders placed on the field. The defenders do not change their positions but if a winger's distance from a defender is not more than d meters, it will automatically tackle him. A robot defender may tackle at most once. On the beginning of the trial, a winger stands on the left edge of the field (across the length) with a soccer ball. Now, his task is to avoid the obstructions of the robot defenders and reach the rightmost edge of the field with the ball. Please tell him the minimum number of tackles he must face in order to reach the opposite end. A player must not go outside the field or he will be disqualified.
Input
Every test case begins with 4 integers, L (1<=L<=10000), W (1<=W<=10000), N (1<=N<=100) & d (1<=d<=1000), as described above. Each of the following N lines contain 2 integers each, defining the x & y co-ordinates of a defender. You can consider the co-ordinate of the lower-left corner of the field to be (0,0) and upper-right corner to be (L,W). Obviously, all the defenders are located inside the field.
The end of input will be marked by a case with L=W=N=d=0. This case should not be processed.
Output
For each test case, print a line in the format, “Case X: Y”, where X is the case number & Y is the minimum number of tackles that needs to be dealt with.
|
Sample Input |
Sample Output |
|
500 300 5 100 |
Case 1: 1 |
Problem Setter: Mohammad Mahmudur Rahman, Special Thanks: Manzurur Rahman Khan