28624번 - Большой потоп 다국어

Водопровод в Готэм--Сити представляет из себя систему из $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$.

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

В первом тестовом примере в каждой подсистеме одна башня. Башню из первой подсистемы можно взорвать на девятой секунде, и получить $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$.