Dreamers eTrip

All submissions for this problem are available.
Smit dreams of him being a King of a state. His story goes as follows,
He fancies to create a state with N cities with M unidirectional roads between them. Initially none of the roads are ready for carrying heavy vehicles (incl. Smit's Maruti 800). So, he plans to donate money to the person responsible of each road, so that the construction of the roads can be done at the rate of 'b' units a day. In general construction rate of a road is given by r(t) = a+b*t where t is the time in day. The tuple (a,b) may be different for different roads. If the value of r(t) becomes >= 0, Smit declares that the road is constructed and is ready for use.
Smit wants to visit all his cities everyday. He desires to visit all the cities everyday before he returns to the capital from where he starts the day. His strategy for a given day is as follows,
 He must visit any city only once.
 Let's say he starts from a city c1, he leaves his food there. He can go to the other cities like c2, c3 and ck using the unidirectional roads. After completing his visit he returns back to c1 to have food. Now, he removes all the cities c1, c2.. ck from the list of cities to visit and starts from some other city d1 (leaves his food here) and and visits the cities which are not already visited like d2, d3.. dk_1 before returning for his food which is at d1. Again he removes the cities d1, d2.. dk_1 before starting from another city e1(if any). This goes on until he visits all the cities in this fashion. We can safely assume that he flies from city c1 to d1(if any) and then to e1(if any) and so on. Here let's call each set of cities he visits like {c1, c2,.. ck}, {d1, d2.. dk1} to be a Mission. Also he assumes that in a particular mission if he doesn't visit more than one city, people of his state will think that he is lazy. So, he tries to avoid such scenarios ie., he desires ot have k, k1.. > 1.
He orders his minister Dhanvin to devise a strategy to visit all the cities (which is famously known as Operation) according to the rules he posed. Also Smit tells him to find the day on which he can start the Operation and also he wants to start Operation as soon as possible. Once he starts his first Operation, he orders to stop the construction of all the roads and destroy the ones that are incomplete. During each Operation, Smit plans to collect tax from the people living in each road. The total tax payable by all the people of a road is given by the function tax(t_1) = c + d*t_1 here the time 't_1' starts from the day Smit does his first Operation i.e., t_1 = 0 on the first Operation day. As the days pass by, the people get tired paying taxes. So, d is strictly negative. And once tax(t_1) of a road drops to zero, Smit doesn't expect any tax (or get 0) from the people of that road. Dhanvin being jealous of Smit, decides to present a strategy such that Smit collects least amount of tax possible. And also Smit asks Dhavin for the travel plan everyday (every t)
Here comes Chinmay, as cunning as his name sounds, he plans to steal the money Smit collects as tax. And he decides to rob at the end of the day after Smit visits all the cities. But unfortunately he has a bag that can carry maximum of U coins. Chinmay likes to finish this job as soon as possible so that he can escape to Vegas before he dies (he dies on the day t = 10^9 + 1). Busy with his Vegas plans, Chinmay asks you tell him the maximum amount of money he can steal, if he can do that on multiple days, output the minimum time he has to wait after Smit starts the Operation. Also, Chinmay doesn't have time to split the money and put in his bag while robbing Smit. He will take the money if and only if all the money that Smit is carrying can fit in the bag (ie <= U). If Smit can never start the Operation or if Chinmay can never steal any money (> 0) before he dies, print 1.
Input
Input description.
 The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
 The first line of each test case contains two integers N, M, U. N denotes the number of cities and M denotes the number of one way roads between the cities. U denotes the size of the bag Chinmay is carrying.Then M lines follow. the ith line describes the ith connection. It contains six space separated integers u v a_i b_i c_i d_i. Here u != v. This means there is an unidirectional road from u to v. Note that u and v are 1indexed. And the construction rate r(t) for this road is given by "a_i+b_i*t" and the tax function tax(t_1) is given by "c_i+d_i*t_1".
Output
Output description.
 For each test case, print three space separated integers. First, the minimum time Smit has to wait to start his Operation. Let's assume the time starts from 0. Second, the maximum amount of money Chinmay can steal and what is the minimum time he has to wait to rob that amount after Smit starts the Operation. If atleast one of scenarios is not possible print "1" (Quotes are for clarity. Don't print them)
Constraints
 1 ≤ T ≤ 10
 2 ≤ N ≤ 200
 1 ≤ M ≤ 5000
 1 ≤ U ≤ 10^9
 10^9 ≤ a_i ≤ 0
 1 ≤ b_i ≤ 100
 10^9 ≤ c_i ≤ 10^9
 100 ≤ d_i < 0
 Here ^ denotes the power function.
Example
Input: 3 3 3 10 1 2 4 6 5 2 1 3 2 1 3 1 2 3 10 4 1 2 3 3 1 1 2 5 1 10 4 2 3 5 1 10 1 3 1 1 1 5 1 2 2 2 1 2 4 2 10 5 2 1 3 1 6 3 Output: 1 5 1 9 1
Explanation
Example case 1.
Here Smit can never start his Operation as he can't visit all the cities according the rules.
Example case 2.
Here Smit can start his Operation on day 5. Chinmay plans to steal 9 days after Smit starts the Operation. i.e., on day 14.
Example case 3.
Here though Smit starts his Operation on day 3. Chinmay can never steal from his as Smit always has > 2 coins or no coins with him. And Chinmay dislikes stealing 0 coins (so does everyone!)
Author:  karthikabinav 
Tags  karthikabinav 
Date Added:  3012014 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, GO 
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. 