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

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

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

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

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