408273: GYM103075 F Рудольф и дорога в университет

F. Рудольф и дорога в университетограничение по времени на тест2 секундыограничение по памяти на тест64 мегабайтавводстандартный вводвыводстандартный вывод

Случилось страшное — Рудольф почти проспал начало собственной лекции! Сейчас он в спешке собирается, надеясь всё же успеть в университет.

На пути от дома Рудольфа до университета есть $$$N$$$ остановок общественного транспорта; дом Рудольфа находится у первой остановки, университет — у $$$N$$$-й. Таким образом, путь разделён на $$$(N - 1)$$$ участков между последовательными остановками.

Каждый участок пути Рудольф может преодолеть либо пешком, либо на маршрутке:

• Если Рудольф преодолевает $$$i$$$-й участок пешком, то он тратит $$$A_i$$$ минут, а его усталость увеличивается на $$$X_i$$$ единиц;
• Если Рудольф преодолевает $$$i$$$-й участок на маршрутке, то он тратит $$$B_i$$$ минут и $$$Y_i$$$ рублей (обратите внимание, что для каждого участка проезд оплачивается отдельно). Кроме того, в маршрутке Рудольф отдыхает, в результате чего его усталость становится равной 0.

Лекция Рудольфа должна начаться через $$$T$$$ минут, а в кармане спешно надетой куртки он нашёл $$$C$$$ рублей, которые может потратить на оплату маршруток.

Рудольф очень волнуется и никак не может спланировать оптимальный маршрут. Помогите ему определить, какое наименьшее максимальное количество усталости он может получить в дороге, добравшись до университета не более чем за $$$T$$$ минут и потратив на проезд не более $$$C$$$ рублей.

Входные данные

Первая строка содержит целые числа $$$N$$$, $$$C$$$ и $$$T$$$ ($$$2 \le N \le 50$$$, $$$1 \le C \le 1000$$$, $$$1 \le T \le 10^9$$$) — соответственно количество остановок на пути от дома до университета, бюджет Рудольфа в рублях и количество минут до начала занятий.

Следующие $$$(N - 1)$$$ строк описывают участки пути. Каждая из них содержит целые числа $$$A_i$$$, $$$X_i$$$, $$$B_i$$$ и $$$Y_i$$$ ($$$1 \le A_i, B_i \le 10^6$$$, $$$1 \le X_i \le 10^6$$$, $$$1 \le Y_i \le 50$$$) — соответственно время преодоления участка пешком в минутах, количество получаемой усталости, время преодоления участка на маршрутке в минутах и стоимость проезда на маршрутке в рублях.

Выходные данные

Если Рудольф не сможет уложиться в отведённые время и бюджет, выведите -1.

Иначе в первой строке выведите одно целое число — наименьшее максимальное количество усталости, которое Рудольф может себе позволить.

Во второй строке выведите $$$(N - 1)$$$ целых чисел, описывающих оптимальный маршрут Рудольфа: если $$$i$$$-й участок необходимо преодолеть пешком, $$$i$$$-е число должно быть равно 0, иначе — 1. Если подходящих ответов несколько, выведите любой из них.

ПримерыВходные данные

5 50 30
10 1 5 20
10 1 5 50
10 4 5 30
10 3 5 30

Выходные данные

3
1 0 1 0 

Входные данные

2 50 30
50 1 35 10

Выходные данные

-1