409519: GYM103608 B Большой потоп

B. Большой потопограничение по времени на тест1 секундаограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Водопровод в Готэм–Сити представляет из себя систему из $$$n$$$ подсистем водонапорных башен. Подсистема номер $$$i$$$ состоит из $$$b_i$$$ независимых башен, каждая из которых в данный момент содержит $$$a_i$$$ единиц воды. Каждую секунду уровень воды в каждой башне увеличивается на $$$1$$$. Через ровно $$$t_i$$$ секунд во всех башнях $$$i$$$-й подсистемы включается водосброс в канализацию, то есть уровень воды в каждой из башен становится равен $$$0$$$ и перестает увеличиваться.

Незадолго до поимки Загадочник заминировал все башни в каждой из $$$n$$$ подсистем. После взрыва любой башни вся имевшаяся на тот момент в башне вода выливается на улицы города, а подача новой воды прекращается. Таким образом, если взорвать башню $$$i$$$-й подсистемы в момент времени $$$t < t_i$$$, на улицы города выльется $$$a_i + t$$$ воды. При этом, взрыв одной из башен подсистемы не влияет на другие башни этой подсистемы.

У Загадочника есть пульты для дистанционного взрыва каждой башни города. Каждую секунду он может выбрать не более $$$k$$$ (возможно, ноль) водонапорных башен и взорвать их. Злодей хочет выбрать порядок взрывов так, чтобы как можно больше воды вытекло на улицы города (вода, стекшая в результате водосброса, не считается).

Бэтмэн опасается действий своего врага, поэтому хочет узнать, какое максимальное количество воды суммарно может оказаться на улицах города?

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

В первой строке ввода через пробел даны два целых числа $$$n$$$ и $$$k$$$ ($$$1 \leqslant n \leqslant 10^5$$$, $$$1 \leqslant k \leqslant 10^9$$$) — количество подсистем водонапорных башен в городе и максимальное количество башен, которые можно взорвать за одну секунду.

В следующих $$$n$$$ строках перечислены описания подсистем, $$$i$$$-я из строк содержит три целых числа, разделенных пробелом — $$$t_i$$$, $$$a_i$$$ и $$$b_i$$$ — секунда, в которую происходит водосброс, изначальный уровень воды в башнях $$$i$$$-й подсистемы и количество башен в подсистеме ($$$1 \leqslant t_i, b_i \leqslant 10^9$$$, $$$1 \leqslant a_i \leqslant 10^4$$$). Гарантируется, что сумма $$$b_i$$$ по всем $$$i$$$ не превосходит $$$10^9$$$.

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

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

Система оценки

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи и необходимых подзадач, а также тесты из условия успешно пройдены.

Подзадача	Баллы	Дополнительные ограничения	Необходимые подзадачи	Информация о проверке
1	10	суммарное количество башен $$$\leqslant 5$$$; $$$t_i \leqslant 5$$$ для всех $$$i$$$; $$$k = 1$$$	–	полная
2	15	$$$k = 1$$$; $$$b_i = 1$$$ для всех $$$i$$$; все $$$t_i$$$ различны	–	полная
3	10	все $$$t_i$$$ равны между собой	–	полная
4	20	$$$b_i = 1$$$ для всех $$$i$$$	2	полная
5	20	$$$t_i \leqslant 10^5$$$ для всех $$$i$$$	1	первая ошибка
6	25	нет	1 – 5	первая ошибка

ПримерыВходные данные

3 2
10 3 1
2 2 1
4 1 1

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

19

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

3 1
10 3 7
2 2 3
4 1 1

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

69

Примечание

В первом тестовом примере в каждой подсистеме одна башня. Башню из первой подсистемы можно взорвать на девятой секунде, и получить $$$3 + 9 = 12$$$ воды; башню из второй подсистемы — на первой секунде, и получить $$$2 + 1 = 3$$$ воды; третьей подсистемы — на третьей секунде, и получить $$$1 + 3 = 4$$$. Итого, мы получим $$$12 + 3 + 4 = 19$$$ единиц воды. Заметим, что от каждой башни мы получили максимально возможное количество воды, поэтому ответ максимальный.

Во втором примере одну башню второй подсистемы стоит взорвать на первой секунде, а остальные гарантированно будут сброшены в канализацию. Башню третьей подсистемы можно взорвать на второй или третьей секунде, но за секунды с четвертой по девятую невозможно успеть взорвать все $$$7$$$ башен первой подсистемы. Поэтому, если взрывать башню третьей подсистемы на третьей секунде, то во вторую секунду стоит взорвать одну башню первой подсистемы. В обоих случаях ответ будет одинаковый и равный $$$((2 + 1)) + ((1 + 2)) + ((3 + 3) + (3 + 4) + \ldots + (3 + 9)) = 69$$$.