Два коровника расположены в позициях от 0 до l на числовой прямой. n коров расположены в разных местах на этой числовой прямой (коровники и коровы являются точками). Каждая корова i изначально находится в некоторой позиции xi и движется в положительном или отрицательном направлении со скоростью одна единица в секунду, представленная целым числом di, равное либо 1, либо -1. Каждая корова также имеет вес wi в диапазоне [1, 103]. Все коровы движутся с постоянной скоростью, пока не произойдет одно из следующих событий:

• Если корова i достигает коровника, то она останавливается.
• Встреча происходит, когда две коровы i и j занимают одну и ту же точку, причем эта точка не является коровником. В этом случае корове i назначается предыдущая скорость коровы j и наоборот. Обратите внимание, что коровы могут встретиться в точках, которые не являются целыми числами.

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

Входные данные

Первая строка содержит два целых числа n (1 ≤ n ≤ 5 * 104) и l (1 ≤ l ≤ 109). Следующие n строк содержат по три целых числа wi, xi и di. Все местоположения xi различны и удовлетворяют неравенству 0 < xi < l.

Выходные данные

Выведите строку, содержащую ответ.

Пример

Коровы в этом примере передвигаются следующим образом:

• Первая и вторая коровы встречаются в точке 1.5 в момент времени 0.5. У первой коровы теперь скорость -1, а у второй скорость 1.
• Вторая и третья коровы встречаются в точке 2 в момент времени 1. У второй коровы теперь скорость -1, а у третьей 1.
• Первая корова достигает левого коровника в момент времени 2.
• Вторая корова достигает левого коровника в момент времени 3.
• Теперь процесс завершается, так как сумма веса коров, достигших коровника, составляет не менее половины суммы веса всех коров. Третья корова достигнет правого коровника в момент времени 4.

Произошло ровно две встречи.