D. Google Code Jam
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наверное, многим знакомы правила раундов Google Code Jam. Напомним основные моменты, важные для решения этой задачи. В течение раунда участникам предлагается решить несколько задач, каждая из которых разбита на две подзадачи: легкую с маленькими ограничениями (Small input), и сложную с большими ограничениями (Large input). Отправить решение сложной подзадачи разрешается только после того, как участник решил легкую подзадачу данной задачи. Других ограничений на порядок решения задач нет. В частности, участник может сначала решить легкую подзадачу, потом переключиться на другую задачу, и только потом вернуться к сложной подзадаче. За решение каждой подзадачи участник получает некоторое количество очков (обычно, различное для каждой задачи). При этом учитываются только полные решения, правильно работающие на всех тестах. Результат тестирования легкой подзадачи сообщается участнику сразу же после отправки, а результат тестирования сложной подзадачи становится известен только после конца раунда. В итоговой таблице результатов участники упорядочиваются по невозрастанию суммы полученных очков. При равенстве очков, участники упорядочиваются по возрастанию штрафного времени. Штрафное время в раундах по правилам Google Code Jam — это время отправки последнего правильного решения.

На очередном раунде Вася решил попробовать новую тактику. Как только соревнование началось, он быстро прочитал все задачи и точно оценил время, необходимое для их решения. Более конкретно, для каждой из n задач Вася знает 5 величин:

  • За решение легкой подзадачи i-ой задачи участник получает scoreSmalli очков, а за решение сложной подзадачи — еще scoreLargei очков. То есть максимальное количество очков, которое можно получить за i-ую задачу равно scoreSmalli + scoreLargei.
  • Чтобы написать решение легкой подзадачи i-ой задачи, Васе требуется ровно timeSmalli минут. Чтобы улучшить этот код и превратить его в решение сложной подзадачи, Васе требуется еще timeLargei минут.
  • Вася много тренировался, поэтому все легкие подзадачи он решает с первой попытки. Но со сложными подзадачами не все так просто: с вероятностью probFaili решение сложной подзадачи после конца раунда окажется неправильным. Напоминаем, что такие решения никак не учитываются при подсчете очков и не влияют на штрафное время.

Раунд длится t минут. Время чтения задач и отправки решений нужно считать равным нулю. Разрешается сдавать решение ровно в момент окончания раунда.

Вася хочет выбрать набор подзадач и порядок их решения таким образом, чтобы матожидание суммы полученных очков было максимально. Если существует несколько способов сделать это, то ему нужно минимизировать матожидание штрафного времени. Помогите Васе справиться с проблемой.

Входные данные

В первой строке записано два целых числа n и t (1 ≤ n ≤ 1000, 1 ≤ t ≤ 1560). Далее следует n строк по 5 чисел в каждой: scoreSmalli, scoreLargei, timeSmalli, timeLargei, probFaili (1 ≤ scoreSmalli, scoreLargei ≤ 109, 1 ≤ timeSmalli, timeLargei ≤ 1560, 0 ≤ probFaili ≤ 1).

probFaili — вещественные числа, заданные не более чем с 6 знаками после точки. Все остальные числа во входных данных целые.

Выходные данные

Выведите два вещественных числа через пробел — максимальное матожидание суммы полученных очков и минимальное возможное при этом матожидание штрафного времени. Ответ будет засчитан, если абсолютная или относительная погрешность не превосходит 10 - 9.

Примеры
Входные данные
3 40
10 20 15 4 0.5
4 100 21 1 0.99
1 4 1 1 0.25
Выходные данные
24.0 18.875
Входные данные
1 1
100000000 200000000 1 1 0
Выходные данные
100000000 1
Примечание

В первом примере один из оптимальных порядков решения задач:

  1. Легкая подзадача третьей задачи.
  2. Легкая подзадача первой задачи.
  3. Сложная подзадача третьей задачи.
  4. Сложная подзадача первой задачи.

Заметим, что если вместо третьей задачи решить легкую подзадачу второй задачи, то матожидание суммы очков будет таким же, но матожидание штрафного времени будет хуже (38).