BYTEFOOD  Food Shortage in Byteland
Fanatics from the BBFO blew up all the food factories in the Bytelandian capital! Hurry up! There is still some food left in shops. Some shops are located in the centre, others in the suburbs, so Johnny has to decide which of them are worth visiting. Some shops can be very big and have plenty of food in them, others may be so small that food dissappears from them at an alarming rate... So? Help Johnny buy as much food as possible.
There are n open shops, each of them located at position (x_{i},y_{i}), for i=1,...,n, where 0 <= x_{i},y_{i} <= 250. The distances between shops are measured using the Manhattan metric (i.e. as sums of absolute values of differences of x and y coordinates). Besides, every shop is characterized by a linear time function describing how much food is left in the shop at the moment:
where 0 <= a_{i} <= 1000000, 0 <= b_{i} <= 1000, while time is the time (in minutes) that has elapsed from the moment Johnny left the house (assume that Johnny does not live in the same place as any shop). If Johnny decides to stay in a shop, he can buy at most b_{i} units of food per minute. Otherwise, he can move along the ortogonal system of streets of the city at a constant speed of unit distance per minute. Johnny only ever changes the action he is performing at the full minute. Because his family is slowly beginning to starve, he should be back at home not later than m minutes after he left. Since there are thousands of starving families in the capital, Johnny can't spent more that 1 <= c_{i} <= 10 minutes in a shop. Moreover, he will never go into the same shop twice for fear of being lynched...
Input
The first line of input contains a single positive integer t <= 1000, the number of test cases.
Each test case begins with the number of shops in the city 1 <= n <= 1000 and the deadline 1 <= m <= 5000.
Then the following n lines consist of four integers x_{i} y_{i} a_{i} b_{i} c_{i} each, describing the position and the parameters of the function for food availability of the ith shop. At the end of every test case comes a line with two integersp q (between 0 and 250), corresponding to the x and y coordinates of the position of Johnny's house.
All the input data are integers.
Output
Process all test cases. The correct output for the ith test case takes the following form:
i [the number of the test case, in the input order]
s m [s is the number of the target shop and m > 0 is the number of minutes spent in it].
At the end of the series of moves you should always write a line conisting of two zeros ('0 0').
All the output data should be integers.
Scoring
The score of your program is the total amount of food that Johnny bought (summed over all the testcases in which he managed to come back home before the deadline).
Example
Input 4 2 20 0 0 100 5 5 10 0 200 10 10 5 0 2 20 0 0 180 15 10 10 0 200 20 10 5 0 4 101 0 0 1000 20 5 20 0 200 1 5 0 20 5000 200 5 20 20 300 5 10 10 10 1 15 1 0 10 1 5 5 0 Output 1 2 10 0 0 2 1 10 0 0 3 3 5 4 10 2 1 0 0 4 1 5 0 0 Score Score = 1261
hide comments
ankur_gupta54:
20150624 13:44:56
Can anyone please explain the output... because for the given sample input I m getting more score... but on submission its showing wrong answer 

Virat Goyal:
20131228 12:26:19
please elaborate the format of output for different possible cases as I am unable to predict why my code is told to be giving wrong answer 

Aditya Pande:
20120606 09:30:26
why am i getting WA in submission id 7099121

Added by:  mima 
Date:  20040609 
Time limit:  20s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: NODEJS PERL6 VB.NET 
Resource:   