Метрострой

Буровая установка «Мегабур 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$).

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