C. Мороженое
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лето в Берляндии длится $$$n$$$ дней, цена одной порции мороженого в $$$i$$$-й день равна $$$c_i$$$. За лето Таня хочет съесть ровно $$$k$$$ порций мороженого. При этом в $$$i$$$-й день она решила, что съест не менее $$$a_i$$$ порций, но не более $$$b_i$$$ ($$$a_i \le b_i$$$). Иными словами, пусть $$$d_i$$$ равно количеству порций, сколько она съест в $$$i$$$-й день. Тогда $$$d_1+d_2+\dots+d_n=k$$$ и $$$a_i \le d_i \le b_i$$$ для каждого $$$i$$$.

Учитывая, что порции мороженого можно есть только в день покупки, найдите минимальную сумму денег, сколько Таня потратит на мороженое летом.

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

В первой строке записаны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \le n \le 2\cdot10^5$$$, $$$0 \le k \le 10^9$$$) — количество дней и суммарное количество порций мороженого, которое съест Таня за лето.

Далее в $$$n$$$ строках содержатся описания дней, по одному описанию в строке. Каждое описание состоит из трёх целых чисел $$$a_i, b_i, c_i$$$ ($$$0 \le a_i \le b_i \le 10^9$$$, $$$1 \le c_i \le 10^6$$$).

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

Выведите минимальную сумму денег, которую Таня может потратить на мороженое летом. Если у Тани не существует способа так покупать и есть мороженое, чтобы удовлетворить все требования, то выведите -1.

Примеры
Входные данные
3 7
3 5 6
0 3 4
3 3 3
Выходные данные
31
Входные данные
1 45000
40000 50000 100000
Выходные данные
4500000000
Входные данные
3 100
2 10 50
50 60 16
20 21 25
Выходные данные
-1
Входные данные
4 12
2 5 1
1 2 2
2 3 7
3 10 4
Выходные данные
35
Примечание

В первом примере Тане надо съесть $$$3$$$ порции мороженого в первый день, $$$1$$$ порцию мороженого во второй день и $$$3$$$ порции мороженого в третий день. В таком случае, сумма потраченных денег равна $$$3\cdot6+1\cdot4+3\cdot3=31$$$. Можно показать, что любой другой допустимый способ съесть ровно $$$7$$$ порций мороженого потребует больших расходов.