|Codeforces Round #170 (Div. 1)|
Many of you must be familiar with the Google Code Jam round rules. Let us remind you of some key moments that are crucial to solving this problem. During the round, the participants are suggested to solve several problems, each divided into two subproblems: an easy one with small limits (Small input), and a hard one with large limits (Large input). You can submit a solution for Large input only after you've solved the Small input for this problem. There are no other restrictions on the order of solving inputs. In particular, the participant can first solve the Small input, then switch to another problem, and then return to the Large input. Solving each input gives the participant some number of points (usually different for each problem). This takes into account only complete solutions that work correctly on all tests of the input. The participant gets the test result of a Small input right after he submits it, but the test result of a Large input are out only after the round's over. In the final results table the participants are sorted by non-increasing of received points. If the points are equal, the participants are sorted by ascending of time penalty. By the Google Code Jam rules the time penalty is the time when the last correct solution was submitted.
Vasya decided to check out a new tactics on another round. As soon as the round begins, the boy quickly read all the problems and accurately evaluated the time it takes to solve them. Specifically, for each one of the n problems Vasya knows five values:
A round lasts for t minutes. The time for reading problems and submitting solutions can be considered to equal zero. Vasya is allowed to submit a solution exactly at the moment when the round ends.
Vasya wants to choose a set of inputs and the order of their solution so as to make the expectation of the total received points maximum possible. If there are multiple ways to do this, he needs to minimize the expectation of the time penalty. Help Vasya to cope with this problem.
The first line contains two integers n and t (1 ≤ n ≤ 1000, 1 ≤ t ≤ 1560). Then follow n lines, each containing 5 numbers: scoreSmall i, scoreLarge i, timeSmall i, timeLarge i, probFail i (1 ≤ scoreSmall i, scoreLarge i ≤ 109, 1 ≤ timeSmall i, timeLarge i ≤ 1560, 0 ≤ probFail i ≤ 1).
probFail i are real numbers, given with at most 6 digits after the decimal point. All other numbers in the input are integers.
Print two real numbers — the maximum expectation of the total points and the corresponding minimum possible time penalty expectation. The answer will be considered correct if the absolute or relative error doesn't exceed 10 - 9.
10 20 15 4 0.5
4 100 21 1 0.99
1 4 1 1 0.25
100000000 200000000 1 1 0
In the first sample one of the optimal orders of solving problems is:
Note that if you solve the Small input of the second problem instead of two inputs of the third one, then total score expectation will be the same but the time penalty expectation will be worse (38).