Метрострой

Буровая установка «Мегабур 2022» для прокладки туннелей метро Байтсбурга имеет n двигателей. Питание установки устроено таким образом, что на все двигатели подается одно и то же целочисленное напряжение x.

У каждого двигателя есть два режима, если на него подается напряжение x, то i-й двигатель работает в первом режиме, если x ≤ z_i и во втором режиме, если x > z_i.

При этом i-й двигатель характеризуется удельной мощностью a_i в первом режиме и b_i во втором режиме. Это означает, что увеличение напряжения на 1 когда двигатель находится в первом режиме, приводит к увеличению его мощности на a_i, а во втором режиме приводит к увеличению его мощности на b_i. Иначе говоря, при подаче напряжения x, если i-й двигатель находится в первом режиме он работает с мощностью a_ix, а если во втором режиме, то с мощностью a_iz_i + b_i(x - z_i).

Для прокладки туннеля суммарная мощность двигателей должна быть не меньше p. Какое минимальное целочисленное напряжение необходимо подать на установку, чтобы суммарная мощность двигателей была больше или равна p?

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

Первая строка входного файла INPUT.TXT содержит целые числа n и p (1 ≤ n ≤ 100; 1 ≤ p ≤ 10¹²). Следующие n строк описывают двигатели и содержат по три целых числа z_i, a_i, b_i (1 ≤ z_i ≤ 10⁹; 1 ≤ a_i, b_i ≤ 10⁴).

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

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

Примеры

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки]