Автомагистраль
Команда Логарифмической области страны Олимпия собирается на олимпиаду, которая состоится в далеком городе Экспоненциальске. Команда поедет на собственном автобусе. Автомагистраль, соединяющая Логарифмическую область с Экспоненциальском, состоит из N последовательных фрагментов. По каждому фрагменту можно ехать либо по бесплатной дороге, тратя a_i секунд, либо по платной, тратя c_i олимпийских центов и b_i секунд. Между этими фрагментами есть транспортные развязки, через которые можно съехать с одной дороги на другую. Такие перестроения требуют q_i секунд (без разницы, с платной дороги на бесплатную или с бесплатной на платную). При продолжении движения по той же дороге аналогичных задержек не происходит. Сначала можно выехать как на бесплатую дорогу, так и на платную. Завершить путь тоже можно по любой из двух дорог последнего фрагмента. Поэтому, развязки есть только между 1-ым и 2-ым фрагментами, между 2-ым и 3-им, ..., между (N–1)-ым и N-ым.
При поездке на олимпиаду очень важно успеть вовремя, поэтому команду интересует, за какую наименьшую стоимость можно добраться из Логарифмической области в Экспоненциальск, потратив суммарно не более чем T секунд. При возвращении с олимпиады время не настолько критично, и перед командой было поставлено требование заплатить на обратном пути не больше чем S олимпийских центов дорожных сборов. Все затраты времени и дорожные сборы одинаковы при движении в обоих направлениях.
Напишите программу, которая по данным о бесплатных и платных дорогах автомагистрали будет находить:
Наименьшую стоимость, за которую можно доехать на олимпиаду за время, не большее T секунд;
Наименьшее время, за которое можно вернуться с олимпиады, заплатив не больше чем S центов дорожных сборов.
Входные данные
Первая строка содержит три целых числа: N (2 ≤ N ≤ 40) - количество фрагментов магистрали, T (0 ≤ T ≤ 10^16) и S (0 ≤ S ≤ 10^16) - ограничение на суммарное время при поиске первого ответа и ограничение на суммарную стоимость при поиске второго. Вторая строка содержит три целых числа a_1, b_1 и c_1 - время движения по бесплатной и платной дорогах 1-го фрагмента, и цену проезда по платной. Каждая из последующих N – 1 строк содержит по четыре целых числа q_i, a_i, b_i и c_i - сначала время на перестроение между дорогами, потом время движения по бесплатной и платной дорогам этого фрагмента, потом цену проезда по платной. Отметим, что на пути на олимпиаду q_i - время, необходимое на перестроение с (i–1)-го фрагмента на i-ый, а на обратном пути q_i - время, необходимое на перестроение с i-го фрагмента на (i–1)-ый (при условии, что автобус съезжает с платной дороги на бесплатную или наоборот). Все значения a_i, b_i и c_i (1 ≤ i ≤ N) в пределах от 1 до 10^15. Все значения q_i (2 ≤ i ≤ N) в пределах от 0 до 10^9.
Выходные данные
Единственная строка должна содержать два целых числа - стоимость самого дешевого способа доехать на олимпиаду за время, не большее T секунд, и длительность самого быстрого среди способов вернуться с олимпиады, заплатив не более чем S центов дорожных сборов. Если ни одного соответствующего способа не существует, следует вывести -1, как одно из чисел.
Объяснение: Самый дешевый способ за время, не большее 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.