G. Управление потоком
ограничение по времени на тест
6 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У Раджа есть одна физическая сетевая линия, которая соединяет его офис с интернетом. Пропускная способность этой линии составляет $$$b$$$ байт в миллисекунду.

Есть $$$n$$$ пользователей, которые хотели бы использовать эту сетевую линию для передачи некоторых данных. $$$i$$$-й из них будет использовать линию начиная с миллисекунды $$$s_i$$$ и до миллисекунды $$$f_i$$$ включительно. Изначально он установит свою скорость передачи данных в значение $$$d_i$$$. Это означает, что он будет использовать скорость передачи данных, равную $$$d_i$$$, в течение миллисекунды $$$s_i$$$, а затем она будет меняться в соответствии с процедурой, описанной ниже.

Контроль за соблюдением пропускной способности линии происходит следующим образом. Предположим, что есть $$$m$$$ пользователей, пытающихся передать какие-то данные по заданной сетевой линии в течение миллисекунды $$$x$$$. Обозначим за $$$t_i$$$ скорость передачи данных у $$$i$$$-м из этих $$$m$$$ пользователей в начале данной миллисекунды. Все $$$t_i$$$ являются целыми неотрицательными значениями.

  • Если $$$m = 0$$$, то есть в течение этой миллисекунды нет пользователей, пытающихся передать данные, ничего не происходит.
  • Если сумма всех $$$t_i$$$ меньше или равна $$$b$$$, то каждый активный пользователь успешно завершает свою передачу данных ($$$i$$$-й активный пользователь передаёт $$$t_i$$$ байт). После этого скорость передачи данных каждого активного пользователя увеличивается на $$$1$$$, то есть каждое $$$t_i$$$ увеличивается на $$$1$$$.
  • Если сумма всех $$$t_i$$$ больше, чем $$$b$$$, то возникает перегрузка линии и в эту миллисекунду вообще никому не удаётся передать данные. В таком случае каждое значение $$$t_i$$$ уменьшается вдвое, то есть каждое $$$t_i$$$ заменяется на $$$\lfloor \frac{t_i}{2} \rfloor$$$.

Радж знает все значения $$$n$$$, $$$b$$$, $$$s_i$$$, $$$f_i$$$ и $$$d_i$$$, он хочет подсчитать общее количество байтов, переданных всеми пользователями в совокупности.

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

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$b$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq b \leq 10^9$$$) — количество пользователей, которые будут использовать линию и пропускная способность линии соответственно.

Каждая из следующих $$$n$$$ строк содержит три целых числа $$$s_i$$$, $$$f_i$$$ и $$$d_i$$$ ($$$1 \leq s_i \leq f_i \leq 10^9$$$, $$$1 \leq d_i \leq 10^9$$$), обозначающих что $$$i$$$-й пользователь будет пытаться передавать данные каждую миллисекунду между $$$s_i$$$ и $$$f_i$$$ включительно, и начальная скорость передачи данных $$$i$$$-го пользователя.

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

Выведите одно целое число — общее количество байтов, которое все пользователи успешно передадут.

Примеры
Входные данные
1 3
1 5 2
Выходные данные
10
Входные данные
1 10
7 11 1000
Выходные данные
0
Входные данные
2 6
1 12 1
8 20 3
Выходные данные
64
Входные данные
3 10
1 100 1
30 60 20
40 80 6
Выходные данные
534
Примечание

Рассмотрим первый пример.

  • Миллисекунда $$$1$$$: Пользователь $$$1$$$ передает $$$2$$$ байта.
  • Миллисекунда $$$2$$$: Пользователь $$$1$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$3$$$: Возникает перегрузка, и никто не передает данные.
  • Миллисекунда $$$4$$$: Пользователь $$$1$$$ передает $$$2$$$ байта.
  • Миллисекунда $$$5$$$: Пользователь $$$1$$$ передает $$$3$$$ байта.

Во втором примере в каждую миллисекунду с $$$7$$$-й по $$$11$$$-ю включительно возникает перегрузка, и единственный пользователь уменьшает свою скорость вдвое. Однако он не успевает достаточно снизить скорость до отключения.

Рассмотрим третий пример.

  • Миллисекунда $$$1$$$: Пользователь $$$1$$$ передает $$$1$$$ байт.
  • Миллисекунда $$$2$$$: Пользователь $$$1$$$ передает $$$2$$$ байта.
  • Миллисекунда $$$3$$$: Пользователь $$$1$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$4$$$: Пользователь $$$1$$$ передает $$$4$$$ байта.
  • Миллисекунда $$$5$$$: Пользователь $$$1$$$ передает $$$5$$$ байтов.
  • Миллисекунда $$$6$$$: Пользователь $$$1$$$ передает $$$6$$$ байтов.
  • Миллисекунда $$$7$$$: Возникает перегрузка, и никто не передает данные.
  • Миллисекунда $$$8$$$: Пользователь $$$1$$$ передает $$$3$$$ байта. Пользователь $$$2$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$9$$$: Возникает перегрузка, и никто не передает данные.
  • Миллисекунда $$$10$$$: Пользователь $$$1$$$ передает $$$2$$$ байта. Пользователь $$$2$$$ передает $$$2$$$ байта.
  • Миллисекунда $$$11$$$: Пользователь $$$1$$$ передает $$$3$$$ байта. Пользователь $$$2$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$12$$$: Возникает перегрузка, и никто не передает данные.
  • Миллисекунда $$$13$$$: Пользователь $$$2$$$ передает $$$2$$$ байта.
  • Миллисекунда $$$14$$$: Пользователь $$$2$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$15$$$: Пользователь $$$2$$$ передает $$$4$$$ байта.
  • Миллисекунда $$$16$$$: Пользователь $$$2$$$ передает $$$5$$$ байтов.
  • Миллисекунда $$$17$$$: Пользователь $$$2$$$ передает $$$6$$$ байтов.
  • Миллисекунда $$$18$$$: Возникает перегрузка, и никто не передает данные.
  • Миллисекунда $$$19$$$: Пользователь $$$2$$$ передает $$$3$$$ байта.
  • Миллисекунда $$$20$$$: Пользователь $$$2$$$ передает $$$4$$$ байта.