Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 3450
Doraemon's Railgun

Time Limit: 2 Seconds      Memory Limit: 65536 KB

toaru-dorano-railgun

Doraemon's city is being attacked again. This time Doraemon has built a powerful railgun in the city. So he will use it to attack enemy outside the city.

There are N groups of enemy. Now each group is staying outside of the city. Group i is located at different (Xi, Yi) and contains Wi soldiers. After T0 days, all the enemy will begin to attack the city. Before it, the railgun can fire artillery shells to them.

The railgun is located at (X0, Y0), which can fire one group at one time, The artillery shell will fly straightly to the enemy. But in case there are several groups in a straight line, the railgun can only eliminate the nearest one first if Doraemon wants to attack further one. It took Ti days to eliminate group i. Now please calculate the maximum number of soldiers it can eliminate.

Input

There are multiple cases. At the first line of each case, there will be four integers, X0, Y0, N, T0 (-1000000000 ≤ X0, Y0 ≤ 1000000000; 1 ≤ N ≤ 500; 1 ≤ T0 ≤ 10000). Next N lines follow, each line contains four integers, Xi, Yi, Ti, Wi (-1000000000 ≤ Xi, Yi ≤ 1000000000; 0 ≤ Ti, Wi ≤ 10000).

Output

For each case, output one integer, which is the maximum number of soldiers the railgun can eliminate.

Sample Input

0 0 5 10
0 5 2 3
0 10 2 8
3 2 4 6
6 7 3 9
4 4 10 2

Sample Output

20

Author: XU, Shicheng; (data: WU, Zejun)
Contest: ZOJ Monthly, December 2010
Submit    Status