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

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

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

Подзадачи