Региональная студенческая предметная олимпиада по информатике (предмет) 2017 г.

Соревнование завершилось 09.04.17 в 16:00

F. Оптимальный тех. режим (170 баллов)

Ограничение по времени: 1 с.
Ограничение по памяти: 256 МБ

Один очень влиятельный и богатый магнат Владимир имеет в своем владении огромное количество нефтедобывающих скважин.

Но вот незадача: в мире нет покупателей на всю его нефть, и продать он может только то количество нефти, на которое нашёл покупателей.

При этом скважины будут работать не на полную мощность, а на какую-то часть от максимальной. Объем добычи каждой скважины подчиняется общему закону:

\displaystyle Q(p)=1337 \cdot p + 2017

Крайне важно, чтобы скважины, по возможности, работали в оптимальном режиме, и жизненно необходимо, чтобы они работали в допустимом. Считается, что скважина работает в оптимальном режиме, если рабочее давление удовлетворяет следующему условию:

\displaystyle p^{opt}_{min} \leqslant p \leqslant p^{opt}_{max}

Критерий работы в допустимом режиме:

\displaystyle p_{min} \leqslant p \leqslant p_{max}

По заданному целевому объему, оптимальным и допустимым режимам каждой скважины определите максимальное количество скважин, работающих в оптимальном режиме, при котором будет обеспечен целевой дебит, а также давление для каждой из скважин.

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

Первая строка входного файла содержит два целых числа: n — количество скважин (1 \leqslant n \leqslant 10^5) и Q — целевой объем добычи (0 \leqslant Q \leqslant 1337067700000).

Последующие n строк содержат по 4 целых числа p_{min}, p^{opt}_{min}, p^{opt}_{max}, p_{max}: минимально допустимое, минимально оптимальное, максимально оптимальное и максимально допустимое значения давления скважины (0 \leqslant p_{min} < p^{opt}_{min} < p^{opt}_{max} < p_{max} < 10^4).

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

В первой строке необходимо вывести максимальное количество скважин, работающих в оптимальном режиме, при котором будет обеспечена целевая добыча.

В следующей строке необходимо вывести n чисел — значения давлений каждой скважины. Ответ будет считаться верным, если абсолютная или относительная погрешность целевой добычи не будет превышать 10^{-4}.

Если ответов существует несколько, вывести любой.

Если ответа не существует, вывести одно число -1.

Примеры
Стандартный вводСтандартный вывод
3 79586
1 5 10 15
1 15 20 25
1 2 3 40
2
7.5 17.5 30