Зустрічі
Два корівники розташовані на числовій прямій у позиціях від 0 до l. n корів знаходяться в різних точках цієї прямої (коровники і корови є точками). Кожна корова i спочатку перебуває в позиції x[i] і рухається в позитивному або негативному напрямку зі швидкістю одна одиниця в секунду, що позначається цілим числом d[i], яке може бути або 1, або -1. Кожна корова також має вагу w[i], яка знаходиться в діапазоні від 1 до 10^3. Усі корови рухаються з постійною швидкістю, поки не відбудеться одна з наступних подій:
Якщо корова i досягає корівника, вона зупиняється.
Зустріч відбувається, коли дві корови i і j опиняються в одній точці, яка не є корівником. У цьому випадку корові i призначається попередня швидкість корови j і навпаки. Зверніть увагу, що корови можуть зустрітися в точках, які не є цілими числами.
Нехай t буде найранішим моментом часу, коли сума ваг корів, що перестали рухатися (через досягнення одного з корівників), становить принаймні половину суми ваг усіх корів. Визначте загальну кількість зустрічей між парами корів у проміжку часу від 0 до t (включно).
Вхідні дані
Перший рядок містить два цілі числа n (1 ≤ n ≤ 5 * 10^4) і l (1 ≤ l ≤ 10^9). Наступні n рядків містять по три цілі числа w[i], x[i] і d[i]. Усі позиції x[i] різні і задовольняють нерівності 0 < x[i] < l.
Вихідні дані
Виведіть одне число — відповідь.
Приклад
Корови в цьому прикладі рухаються наступним чином:
Перша і друга корови зустрічаються в точці 1.5 в момент часу 0.5. У першої корови тепер швидкість -1, а у другої швидкість 1.
Друга і третя корови зустрічаються в точці 2 в момент часу 1. У другої корови тепер швидкість -1, а у третьої 1.
Перша корова досягає лівого корівника в момент часу 2.
Друга корова досягає лівого корівника в момент часу 3.
Тепер процес завершується, оскільки сума ваг корів, що досягли корівника, складає не менше половини суми ваг усіх корів. Третя корова досягне правого корівника в момент часу 4.
Сталося рівно дві зустрічі.