Food Shortage in Byteland

All submissions for this problem are available.
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
Author:  admin 
Tags  admin 
Date Added:  1122008 
Time Limit:  1.45 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, kotlin, TEXT, SCM chicken, CLOJ, COB, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 