B. Заказ пиццы
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Проходит очередной финал Start[c]up, поэтому необходимо заказать пиццу для финалистов, участвующих в соревновании в офисе компании. Существует всего два типа пиццы (конечно нет, но в этой задаче будем считать, что да), все пиццы содержат одинаковое число S кусочков.

Известно, что i-й участниц съест si кусочков пиццы, и получит ai единиц счастья от съедания каждого кусочка пиццы первого типа, и bi единиц счастья от съедания каждого кусочка пиццы второго типа. Мы можем заказать любое число пицц первого и второго типов, но мы хотим заказать минимальное число пицц, необходимое для того, чтобы все участники могли съесть необходимое каждому число кусочков. Учитывая это ограничение, какое максимальное суммарное число единиц счастья могут получить участники?

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

Первая строка содержит целые числа N и S (1 ≤ N ≤ 105, 1 ≤ S ≤ 105) — число участников и число кусочков пиццы в каждой пицце, соответственно.

Далее следуют N строк. i-я из них содержит целые числа si, ai и bi (1 ≤ si ≤ 105, 1 ≤ ai ≤ 105, 1 ≤ bi ≤ 105) — количество кусочков пиццы, которые съест i-й участник, счастье, которое он получает от каждого съеденного кусочка первого типа, и счастье, которое он получает от каждого съеденного кусочка второго типа, соответственно.

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

Выведите максимальное суммарное счастье, которое могут получить участники.

Примеры
Входные данные
3 12
3 5 7
4 6 7
5 9 5
Выходные данные
84
Входные данные
6 10
7 4 7
5 8 8
12 5 8
6 11 6
3 3 7
5 9 6
Выходные данные
314
Примечание

В первом примере нужно купить лишь одну пиццу. Если это будет пицца первого типа, то суммарное счастье будет равно 3·5 + 4·6 + 5·9 = 84, а если купить пиццу второго типа — то суммарное счастье будет равно 3·7 + 4·7 + 5·5 = 74.