28412번 - Метрострой 서브태스크다국어

문제

Буровая установка «Мегабур 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_ix,ドル а если во втором режиме, то с мощностью $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$).

출력

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

제한

서브태스크

힌트