Задача №111146. Автомагистраль
Команда Логарифмической области страны Олимпия собирается на олимпиаду, которая состоится в далеком городе Экспоненциальске. Команда поедет на собственном автобусе. Автомагистраль, соединяющая Логарифмическую область с Экспоненциальском, состоит из N последовательных фрагментов. По каждому фрагменту можно ехать либо по бесплатной дороге, тратя ai секунд, либо по платной, тратя ci олимпийских центов и bi секунд. Между этими фрагментами есть транспортные развязки, через которые можно съехать с одной дороги на другую. Такие перестроения требуют qi секунд (без разницы, с платной дороги на бесплатную или с бесплатной на платную). При продолжении движения по той же дороге аналогичных задержек не происходит. Сначала можно выехать как на бесплатую дорогу, так и на платную. Завершить путь тоже можно по любой из двух дорог последнего фрагмента. Поэтому, развязки есть только между 1-м и 2-м фрагментами, между 2-м и 3-м, ..., между (N–1)-м и N-м.
При поездке на олимпиаду очень важно успеть вовремя, поэтому команду интересует, за какую наименьшую стоимость можно добраться из Логарифмической области в Экспоненциальск, потратив суммарно не более чем T секунд. При возвращении с олимпиады время не настолько критично, и перед командой было поставлено требование заплатить на обратном пути не больше чем S олимпийских центов дорожных сборов. Все затраты времени и дорожные сборы одинаковы при движении в обоих направлениях.
Напишите программу, которая по данным о бесплатных и платных дорогах автомагистрали будет находить:
- Наименьшую стоимость, за которую можно доехать на олимпиаду за время, не большее T секунд
- Наименьшее время, за которое можно вернуться с олимпиады, заплатив не больше чем S центов дорожных сборов
Первая строка входного файла содержит три целых числа N (2 ≤ N ≤ 40) — количество фрагментов магистрали, T (0 ≤ T ≤ 1016) и S (0 ≤ S ≤ 1016) — ограничение на суммарное время при поиске первого ответа и ограничение на суммарную стоимость при поиске второго. Вторая строка содержит три целых числа a1, b1 и c1 — время движения по бесплатной и платной дорогах 1-го фрагмента, и цену проезда по платной. Каждая из последующих N–1 строк содержит по четыре целых числа qi, ai, bi и ci — сначала время на перестроение между дорогами, потом время движения по бесплатной и платной дорогам этого фрагмента, потом цену проезда по платной. Отметим, что на пути на олимпиаду qi — время, необходимое на перестроение с (i–1)-го фрагмента на i-й, а на обратном пути qi — время, необходимое на перестроение с i-го фрагмента на (i–1)-й (при условии, что автобус съезжает с платной дороги на бесплатную или наоборот). Все значения ai, bi и ci (1 ≤ i ≤ N) в пределах от 1 до 1015. Все значения qi (2 ≤ i ≤ N) в пределах от 0 до 109.
Единственная строка выходного файла должна содержать два целых числа — стоимость самого дешевого способа доехать на олимпиаду за время, не большее T секунд, и длительность самого быстрого среди способов вернуться с олимпиады, заплатив не более чем S центов дорожных сборов. Если ни одного соответствующего способа не существует, следует вывести - 1, как одно из чисел.
5 2012 2012
10000 17 10000
4 1000 17 1000
3 100 17 100
2 10 17 10
1 1 17 1
10000 10051
Объяснение: самый дешевый способ за время, не большее 2012 — проехать 1-й фрагмент по платной дороге, далее по бесплатной: суммарная стоимость 10000 + 0 + 0 + 0 + 0 = 10000 за время 17 + 4(перестроение) + 1000 + 100 + 10 + 1 = 1132. Самый быстрый способ вернуться, заплатив не более 2012 — 5-й и 4-й фрагменты по бесплатной, 3-й и 2-й по платной, 1-й по бесплатной: время 1 + 10 + 2(перестроение) + 17 + 17 + 4(перестроение) + 10000 = 10051 при сумме сборов 0 + 1000 + 100 + 0 + 0 = 1100.
Подзадача 1. N ≤ 17. Решение оценивается в 30 баллов.
Подзадача 2. T, S, все qi, ai, bi и ci не превышают 105. Решение оценивается в 30 баллов.
Подзадача 3. Дополнительные ограничения отсутствуют. Решение оценивается в 40 баллов. Каждый тест оценивается независимо.
Подзадачи являются независимыми (можно получить баллы за вторую подзадачу, при этом не получив за первую).