Автомагістраль
Команда з Логарифмічної області країни Олімпія готується до олімпіади, яка відбудеться в далекому місті Експоненціальськ. Вони вирушать на власному автобусі. Автомагістраль, що з'єднує Логарифмічну область з Експоненціальськом, складається з 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.