Cross the Fire

Our hero is planned to cross an important street, the other side of the street is the headquarters of the enemy. The whole street is a rectangle with length L and width W. Because the streets are sealed of the building block on both up and down side, we assumed people can only walk down on the street but not get out the up and down board.
In order to prevent our hero, the evil enemy layout N mines in the street. Due to internal staff informed in advance, the hero has known the distribution of all mines, and their explosion radius and explosion power. The mine enemy used is an amazing sense-mine, as long as the person come into its sensing radius, it will explode, due to unknown reasons, the explosion radius of each mine is same to its sensing radius. Heroes have a certain strength value at first, but once he touching a mine, he will lose some strength value same to the explosion power of this mine. Once the hero's strength value is not greater than zero, he will die.
Now hero want you to help him calculate whether there is a path so that he can live to reach the enemy headquarters. If he can live to cross the street, he wants to know the maximum remaining strength value after crossing the street. We assume the hero's path trajectory is arbitrary.

The input consists of several test cases.
The first line contains four integers L, W, N and P– the length and the width of the street, the number of mines, and the initial strength value of hero, respectively(1 ≤ L ≤ 10000 ,1 ≤ W ≤ 10000, 1 ≤ N ≤ 250, 1 ≤ P ≤ 1000000). Each of the following N lines contains four integers Xi, Yi, Ri and Pi – the coordinates, the sensing radius(explosion radius) and the explosion power of i-th mine in the street (0 ≤ Xi ≤ L, 0 ≤ Yi ≤ W, 1 ≤ Ri ≤ 100, 1 ≤ Pi ≤ 10000). The coordinates and radius are given in meters, relative to the street: the southwestern corner of the street has coordinates (0, 0), and the northeastern corner of the street has coordinates (L, W).
Note that crossing the street may start at coordinate (0, ys ) for any 0 ≤ ys ≤ W and end at coordinate (L, ye ) for any 0 ≤ ye ≤ W . Neither ys nor ye need to be integer.

For each input cases, if our hero cannot live to cross the street, please output “Our hero has been killed”; otherwise output the maximum remaining strength value after crossing the street.

130 340 5 2
10 50 100 1
130 130 100 1
70 170 100 1
0 180 100 1
60 260 100 1

1

2011 Multi-University Training Contest 10 - Host by HRBEU