Nebius Welcome Round (Div. 1 + Div. 2) |
---|
Закончено |
У Раджа есть одна физическая сетевая линия, которая соединяет его офис с интернетом. Пропускная способность этой линии составляет $$$b$$$ байт в миллисекунду.
Есть $$$n$$$ пользователей, которые хотели бы использовать эту сетевую линию для передачи некоторых данных. $$$i$$$-й из них будет использовать линию начиная с миллисекунды $$$s_i$$$ и до миллисекунды $$$f_i$$$ включительно. Изначально он установит свою скорость передачи данных в значение $$$d_i$$$. Это означает, что он будет использовать скорость передачи данных, равную $$$d_i$$$, в течение миллисекунды $$$s_i$$$, а затем она будет меняться в соответствии с процедурой, описанной ниже.
Контроль за соблюдением пропускной способности линии происходит следующим образом. Предположим, что есть $$$m$$$ пользователей, пытающихся передать какие-то данные по заданной сетевой линии в течение миллисекунды $$$x$$$. Обозначим за $$$t_i$$$ скорость передачи данных у $$$i$$$-м из этих $$$m$$$ пользователей в начале данной миллисекунды. Все $$$t_i$$$ являются целыми неотрицательными значениями.
Радж знает все значения $$$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
Рассмотрим первый пример.
Во втором примере в каждую миллисекунду с $$$7$$$-й по $$$11$$$-ю включительно возникает перегрузка, и единственный пользователь уменьшает свою скорость вдвое. Однако он не успевает достаточно снизить скорость до отключения.
Рассмотрим третий пример.
Название |
---|