Зустрічі#10288

Зустрічі

1 секунда

128 мегабайтів

Дуже легка

Два корівники розташовані на числовій прямій у позиціях $0$ та $l$ . $n$ корів знаходяться в різних точках цієї прямої (коровники і корови є точками). Кожна корова $i$ спочатку перебуває в позиції $x_{i}$ x_i і рухається в позитивному або негативному напрямку зі швидкістю одна одиниця в секунду, що позначається цілим числом $d_{i}$ d_i, яке може бути або $1$ , або $- 1$ . Кожна корова також має вагу $w_{i}$ w_i, яка знаходиться в діапазоні від $1$ до $1 0^{3}$ 10^3. Усі корови рухаються з постійною швидкістю, поки не відбудеться одна з наступних подій:

Якщо корова $i$ досягає корівника, вона зупиняється.
Зустріч відбувається, коли дві корови $i$ і $j$ опиняються в одній точці, яка не є корівником. У цьому випадку корові $i$ призначається попередня швидкість корови $j$ і навпаки. Зверніть увагу, що корови можуть зустрітися в точках, які не є цілими числами.

Нехай $t$ буде найранішим моментом часу, коли сума ваг корів, що перестали рухатися (через досягнення одного з корівників), становить принаймні половину суми ваг усіх корів. Визначте загальну кількість зустрічей між парами корів у проміжку часу від $0$ до $t$ (включно).

Вхідні дані

Перший рядок містить два цілі числа $n$ ( $1 \leq n \leq 5 \cdot 1 0^{4}$ 1 \le n \le 5 \cdot 10^4) і $l$ ( $1 \leq l \leq 1 0^{9}$ 1 \le l \le 10^9). Наступні $n$ рядків містять по три цілі числа $w_{i}$ w_i, $x_{i}$ x_i і $d_{i}$ d_i. Усі позиції $x_{i}$ x_i різні і задовольняють нерівності $0 < x_{i} < l$ 0 < x_i < l.

Вихідні дані

Виведіть одне число — відповідь.

Приклади

Корови в цьому прикладі рухаються наступним чином:

Перша і друга корови зустрічаються в точці $1.5$ в момент часу $0.5$ . У першої корови тепер швидкість $- 1$ , а у другої швидкість $1$ .
Друга і третя корови зустрічаються в точці $2$ в момент часу $1$ . У другої корови тепер швидкість $- 1$ , а у третьої $1$ .
Перша корова досягає лівого корівника в момент часу $2$ .
Друга корова досягає лівого корівника в момент часу $3$ .
Тепер процес завершується, оскільки сума ваг корів, що досягли корівника, складає не менше половини суми ваг усіх корів. Третя корова досягне правого корівника в момент часу $4$ .

Сталося рівно дві зустрічі.

Приклад 1