Задача 3. Метрострой ≡

Условие

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

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

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

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

Формат входных данных

Первая строка ввода содержит целые числа n и p.

Следующие n строк описывают двигатели и содержат по три целых числа z_i, a_i, b_i.

Формат выходных данных

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

Ограничения

1 ≤ n ≤ 100, 1 ≤ p ≤ 10¹²

1 ≤ z_i ≤ 10⁹, 1 ≤ a_i, b_i ≤ 10⁴

Примеры тестов

1 6
4 1 2

5

3 15
2 3 3
4 2 1
5 2 2

3