CF277D.Google Code Jam

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:

• Solving the Small input of the i-th problem gives to the participant scoreSmall__i points, and solving the Large input gives scoreLarge__i more points. That is, the maximum number of points you can get for the i-th problem equals scoreSmall__i + scoreLarge__i.
• Writing the solution for the Small input of the i-th problem takes exactly timeSmall__i minutes for Vasya. Improving this code and turning it into the solution of the Large input takes another timeLarge__i minutes.
• Vasya's had much practice, so he solves all Small inputs from the first attempt. But it's not so easy with the Large input: there is the probFail__i probability that the solution to the Large input will turn out to be wrong at the end of the round. Please keep in mind that these solutions do not affect the participants' points and the time penalty.

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.

许多参赛者一定熟悉 Google Code Jam 比赛轮次的规则。下面我们回顾一些对解决本题至关重要的关键点：在一轮比赛中，参赛者需尝试解决若干道题目，每道题又分为两个子问题：一个限制较宽松的“小数据集”（Small input），以及一个限制较严格的“大数据集”（Large input）。仅当成功解决了某道题的小数据集后，才被允许提交该题的大数据集解法；除此之外，对解题顺序没有任何其他限制。例如，参赛者可以先解决某题的小数据集，然后切换到另一道题，之后再返回去解决前一道题的大数据集。每解决一个数据集，参赛者将获得一定分数（通常每道题的两个数据集分值不同）。该得分仅针对完全正确、能通过该数据集全部测试用例的解法。参赛者提交小数据集后会立即获知评测结果；而大数据集的评测结果则要等到整轮比赛结束后才统一公布。最终成绩排行榜按选手所得总分非递增排序；若总分相同，则按时间罚时（time penalty）升序排序。根据 Google Code Jam 规则，时间罚时定义为最后一条正确提交所对应的时刻。

瓦夏（Vasya）决定在另一轮比赛中尝试一种新策略。比赛一开始，他迅速通读所有题目，并准确预估了解决每道题所需的时间。具体而言，对于 $n$ 道题目中的第 $i$ 题，瓦夏已知以下五个参数：

• 解决第 $i$ 题的小数据集可得 $\text{scoreSmall}_i$ 分，解决其大数据集可额外获得 $\text{scoreLarge}_i$ 分。即，第 $i$ 题最多可获得 $\text{scoreSmall}_i + \text{scoreLarge}_i$ 分。
• 瓦夏编写第 $i$ 题小数据集解法恰好耗时 $\text{timeSmall}_i$ 分钟；在此基础上改进代码、使其能通过大数据集，还需额外耗时 $\text{timeLarge}_i$ 分钟。
• 瓦夏经过大量训练，因此所有小数据集均能在首次提交时即通过；但大数据集则不然：对于第 $i$ 题的大数据集解法，存在 $\text{probFail}_i$ 的概率在比赛结束时被判定为错误。请注意，这些失败的大数据集提交不会影响选手得分，也不会计入时间罚时。

整轮比赛持续 $t$ 分钟。读题与提交解法所用时间可忽略不计（视为 0）。瓦夏允许恰好在比赛结束时刻（即第 $t$ 分钟）提交解法。

瓦夏希望选择一组待解决的数据集（即确定哪些小数据集和对应的大数据集），并安排其求解顺序，使得最终总得分的期望值最大化。若存在多种方案能达到最大期望得分，则需在其中进一步最小化时间罚时的期望值。请帮助瓦夏解决这一问题。

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.

第一行包含两个整数 $n$ 和 $t$（$1 \leq n \leq 1000$，$1 \leq t \leq 1560$）。接下来是 $n$ 行，每行包含 5 个数字：$\text{scoreSmall}_i$、$\text{scoreLarge}_i$、$\text{timeSmall}_i$、$\text{timeLarge}_i$、$\text{probFail}_i$（$1 \leq \text{scoreSmall}_i,\, \text{scoreLarge}_i \leq 10^9$，$1 \leq \text{timeSmall}_i,\, \text{timeLarge}_i \leq 1560$，$0 \leq \text{probFail}_i \leq 1$）。

$\text{probFail}_i$ 是实数，小数点后最多有 6 位数字。输入中的其余所有数字均为整数。

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^{-9}$，则答案视为正确。

In the first sample one of the optimal orders of solving problems is:

1. The Small input of the third problem.
2. The Small input of the first problem.
3. The Large input of the third problem.
4. The Large input of the first problem.

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).

在第一个样例中，一种最优的题目解答顺序为：

1. 第三题的小数据集（Small input）。
2. 第一题的小数据集（Small input）。
3. 第三题的大数据集（Large input）。
4. 第一题的大数据集（Large input）。

注意：若改为解答第二题的小数据集，而非第三题的两个数据集，则总得分期望值相同，但时间罚分期望值会更差（为 38）。