Задача №115210. Метрострой
Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет \(n\) двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение \(x\).
У каждого двигателя есть два режима, если на него подается напряжение \(x\), то \(i\)-й двигатель работает в первом режиме, если \(x \le z_i\) и во втором режиме, если \(x > z_i\).
При этом \(i\)-й двигатель характеризуется удельной мощностью \(a_i\) в первом режиме и \(b_i\) во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на \(a_i\), а во втором режиме приводит к увеличению его мощности на \(b_i\). Иначе говоря, при подаче напряжения \(x\), если \(i\)-й двигатель находится в первом режиме он работает с мощностью \(a_i x\), а если во втором режиме, то с мощностью \(a_iz_i + b_i(x-z_i)\).
Для прокладки туннеля суммарная мощность двигателей должна быть не меньше \(p\). Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна \(p\)?
Первая строка ввода содержит целые числа \(n\) и \(p\) (\(1 \le n \le 100\), \(1 \le p \le 10^{12}\)).
Следующие \(n\) строк описывают двигатели и содержат по три целых числа \(z_i\), \(a_i\), \(b_i\) (\(1 \le z_i \le 10^9\), \(1 \le a_i, b_i \le 10^4\)).
Требуется вывести одно целое число — минимальное напряжение, которые необходимо подать на установку.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 1 | 20 | \(n=1\) | первая ошибка | |
| 2 | 20 | \(a_i, b_i \le 100\), \(p \le 10^5\) | первая ошибка | |
| 3 | 20 | У всех двигателей \(z_i\) одинаковые | 1 | первая ошибка |
| 4 | 20 | \(n \le 2\) | 1 | первая ошибка |
| 5 | 20 | нет | 1–4 | первая ошибка |
1 6 4 1 2
5
3 15 2 3 3 4 2 1 5 2 2
3