Catering Services

All submissions for this problem are available.
Bob, a famous foodie of IIT Kanpur, tired of studying, decides to go into catering startup. Bob plans to cater to the offices located in Kanpur. In Kanpur, all the offices are in some or other apartments. Also, the offices in the same building have same lunch time. Bob, being a good negotiator, acquired contracts for round the clock catering from all offices of N apartments in the city.
For the N apartments in the city, ith apartment housing X[i] offices and and each office is charged P[i] rupees every day for catering at their lunch time, i.e., for time S[i] to E[i]. Each employee in the startup can cater to atmost one office at a time and one employee is enough to complete the catering needs of an office. An employee earns C rupees a day. Also, there are M one way roads in the city, each motorable by bike. The average speed of bike in Kanpur is 1km per V minutes.
Since Bob would want to maximize his profit, he would want to hire minimum number of employees. So, he would send a employee to some office, who after completing his duty, can cater to another office. Thereby, decreasing the number of employees, if possible.
Now, Alice, a very close friend and business partner of Bob, advises him against catering to a specific apartment J. Now Bob cannot refuse her. So, he decided to cater to as many offices of Jth apartment, till his profit does not decrease. Help Bob to find out how many offices of Jth apartment he would serve and also, the maximum profit that he would reap.
Input
First line contains T, number of test cases.
Each Test case begins with line containing N M J C V.
Next N lines follows, each line contain 4 space separated integers, X[i] S[i] E[i] P[i],, for the ith line.
The following M lines contain 3 space separated integers each, I, J and D_{i j}, such that I and J represent apartments and the distance between them is equal to D_{i j}.
Output
The output consists of T lines.
For each test case, print, in different lines, the number of offices catered in apartment J and maximum profit that can be earned.
Constraints
 1 ≤ T ≤ 5
 1 ≤ N ≤ 100
 0 ≤ N ≤ 10
 1 ≤ C ≤ 10^{5}
 1 ≤ X ≤ 10^{6}
 1 ≤ S[i] < E[i] ≤ 10^{9}
 1 ≤ P[i] ≤ 10^{6}
 D_{i j} ≤ 10^{4}
Sample Input
1
3 6 1 100 1
10 40 50 90
4 15 35 110
5 10 20 50
1 2 1
2 1 1
1 3 1
3 1 1
2 3 1
3 2 1
Sample Output
9 600
Explanation
Since Bob has to cater apartment 2 and 3, so atleast 9 employees are required, as lunch time of apartment 2 and 3 are overlapping.
For apartment 1, the same 9 employees can be used for catering as the lunch times do not overlap with apartments 2 and 3 and since employing more people will reduce the profit, total of 9 people are employed.
Hence 9 offices are catered in apartment 1.
The equation for profit is X[2] * P[2] + X[3] * P[3] + 9 * P[1]  9 * C = 600
Author:  iopc_admin 
Tags  iopc_admin 
Date Added:  2022014 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, 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. 