Два амбара расположены в позициях \(0\) и \(L\) \((1\le L\le 10^9)\) на
одномерной числовой прямой. Также имеется \(N\) коров \((1\le N\le 5\cdot 10^4)\)
в различных точках этой числовой прямой (и амбар и коровы представляем точками).
Каждая корова \(i\) изначально расположена в некоторой позиции \(x_i\)
и двигается в положительном или отрицательном направлении со скоростью
одна единица в секунду, представленной целым числом \(d_i\), которое равно
либо \(1\) либо \(-1\).
Каждая корова имеет вес \(w_i\) в интервале \([1,10^3]\). Все коровы всегда
движутся с постоянной скоростью, пока не произойдёт одно из следующих
событий:
- Если корова \(i\) достигает амбара, то она прекращает движение.
- Поисходит встреча, когда две коровы \(i\) и \(j\) находятся в одной точке,
которая не является амбаром. В этом случае корове \(i\) назначается скорость
коровы \(j\) и наоборот. Заметим, что коровы могут встретится в точке,
которая не является целым числом.
Пусть \(T\) - самое раннее время, когда сума весов всех коров, которые
перестали двигаться (достигнув одного из амбаров) составляет как минимум
половину суммы весов всех коров. Определите общее количеаство встреч между
парами коров, которое состоится в интервале времени от \(0 \ldots T\)
(включая время \(T\)).
ОЦЕНИВАНИЕ:
- Тесты 2-4 удовлетворяют \(N\le 10^2\) и \(w_i=1\) для всех \(i.\)
- Тесты 5-7 удовлетворяют \(N\le 10^2.\)
ФОРМАТ ВВОДА (файл meetings.in):
Первая строка содержит два разделённых пробелом целых числа
\(N\) и
\(L\).
Каждая из последующих \(N\) строк содержит тра разделённых пробелом целых числа
\(w_i\), \(x_i\), \(d_i.\)
Все \(x_i\) различные и удовлетворяют \(0<x_i<L.\)
Формат вывода (файл meetings.out):
Выведите одно целое число - ответ задачи.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5
1 1 1
2 2 -1
3 3 -1
|
2
|