Автомагістраль#3038

Автомагістраль

1 секунда

256 мегабайтів

Складна

Команда з Логарифмічного краю Олімпії готується до Олімпіади, яка відбудеться у далекому місті Експоненціальськ. Команда вирушить туди власним автобусом. Автотраса, яка з'єднує Логарифмічний край з Експоненціальськом, складається з $N$ послідовних ділянок. Для кожної ділянки команда може обрати безкоштовну дорогу, яка займає $a_{i}$ a_i секунд, або платну, що коштує $c_{i}$ c_i олімпійських центів і триває $b_{i}$ b_i секунд. Між ділянками є розв'язки, які дозволяють змінювати тип дороги — це займає $q_{i}$ q_i секунд незалежно від напрямку переходу. Якщо продовжувати рух по тій самій дорозі, затримок немає. Подорож можна розпочати як з безкоштовної, так і з платної дороги, і закінчити на будь-якому типі дороги останньої ділянки. Розв'язки існують лише між $1$ -ю і $2$ -ю ділянками, $2$ -ю і $3$ -ю, ..., $(N - 1)$ (N-1)-ю і $N$ -ю ділянками.

На шляху до Олімпіади важливо встигнути вчасно, тому команду цікавить, за яку мінімальну вартість можна дістатися з Логарифмічного краю в Експоненціальськ, витративши не більше ніж $T$ секунд. На зворотному шляху час не критичний, і команда прагне витратити не більше ніж $S$ олімпійських центів на платну дорогу. Всі часи руху і збори однакові у обох напрямках.

Напишіть програму, яка, використовуючи інформацію про безкоштовні та платні дороги, визначить:

Мінімальну вартість проїзду до Олімпіади не більше ніж за $T$ секунд;
Мінімальний час повернення з Олімпіади при витратах на платні дороги не більше $S$ центів.

Вхідні дані

У першому рядку три цілих числа: $N$ ( $2 \leq N \leq 40$ 2 \le N \le 40) — кількість ділянок траси, $T$ ( $0 \leq T \leq 1 0^{16}$ 0 \le T \le 10^{16}) — обмеження часу для першого завдання, та $S$ ( $0 \leq S \leq 1 0^{16}$ 0 \le S \le 10^{16}) — обмеження вартості для другого. У другому рядку три цілих числа $a_{1}$ a_1, $b_{1}$ b_1, $c_{1}$ c_1 — час проходження безкоштовною і платною дорогами першої ділянки та вартість платної. Кожен із наступних $N - 1$ N-1 рядків містить чотири цілих числа $q_{i}$ q_i, $a_{i}$ a_i, $b_{i}$ b_i, $c_{i}$ c_i — час на перехід між дорогами, потім час руху безкоштовною і платною дорогами цієї ділянки та вартість платної дороги. Для поїздки до Олімпіади $q_{i}$ q_i — це час на перехід з $(i - 1)$ (i-1)-ї на $i$ -ту ділянку, а для повернення $q_{i}$ q_i — це час на перехід з $i$ -ї на $(i - 1)$ (i-1)-у ділянку (якщо автобус переходить з платної дороги на безкоштовну або навпаки). Всі $a_{i}$ a_i, $b_{i}$ b_i, $c_{i}$ c_i ( $1 \leq i \leq N$ 1 \le i \le N) — цілі числа від $1$ до $1 0^{15}$ 10^{15}. Всі $q_{i}$ q_i ( $2 \leq i \leq N$ 2 \le i \le N) — цілі числа від $0$ до $1 0^{9}$ 10^9.

Вихідні дані

Виведіть у одному рядку два цілих числа: мінімальну вартість поїздки до Олімпіади не більше ніж за $T$ секунд і мінімальний час повернення з Олімпіади при витратах на платні дороги не більше $S$ олімпійських центів. Якщо жодного підходящого способу не існує, виведіть $- 1$ для відповідної величини.

Приклади

Приклад 1

Примітка

Пояснення: Найдешевший спосіб за $2012$ секунд — їхати першу ділянку платною дорогою, далі — безкоштовною: сумарна вартість $10000 + 0 + 0 + 0 + 0 = 10000$ 10000 + 0 + 0 + 0 + 0 = 10000 за $17 + 4$ 17 + 4 (перехід) $+ 1000 + 100 + 10 + 1 = 1132$ + 1000 + 100 + 10 + 1 = 1132. Найшвидший спосіб повернутися при витратах не більш як $2012$ — $5$ -та і $4$ -та ділянки безкоштовно, $3$ -я і $2$ -га платно, $1$ -ша безкоштовно: час $1 + 10 + 2$ 1 + 10 + 2 (перехід) $+ 17 + 17 + 4$ + 17 + 17 + 4 (перехід) $+ 10000 = 10051$ + 10000 = 10051 із витратами $0 + 1000 + 100 + 0 + 0 = 1100$ 0 + 1000 + 100 + 0 + 0 = 1100.