Дві ферми розташовані в позиціях \(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.\)

Формат вхідних даних

Перший рядок містить два розділені пропуском цілих числа \(N\) і \(L\).

Кожний з наступних \(N\) рядків містить три розділених пробілом цілих числа \(w_i\), \(x_i\), \(d_i.\) Всі \(x_i\) різні і задовольняють \(0<x_i<L.\)

Формат вихідних даних

Виведіть одне ціле число – відповідь задачі.

Приклад вхідних даних

3 5
1 1 1
2 2 -1
3 3 -1

Приклад вихідних даних

2

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

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

Рівно дві зустрічі відбудуться