Встречи
Два коровника расположены в позициях от 0 до l на числовой прямой. n коров расположены в разных местах на этой числовой прямой (коровники и коровы являются точками). Каждая корова i изначально находится в некоторой позиции x[i] и движется в положительном или отрицательном направлении со скоростью одна единица в секунду, представленная целым числом d[i], равное либо 1, либо -1. Каждая корова также имеет вес w[i] в диапазоне [1, 10^3]. Все коровы движутся с постоянной скоростью, пока не произойдет одно из следующих событий:
Если корова i достигает коровника, то она останавливается.
Встреча происходит, когда две коровы i и j занимают одну и ту же точку, причем эта точка не является коровником. В этом случае корове i назначается предыдущая скорость коровы j и наоборот. Обратите внимание, что коровы могут встретиться в точках, которые не являются целыми числами.
Пусть t будет самым ранним моментом времени, когда сумма веса коров, переставших двигаться (из-за того что они достигли одного из коровников), составляет по крайней мере половину суммы веса всех коров. Определите общее количество встреч между парами коров в диапазоне времени 0 ... t (включая время 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.
Произошло ровно две встречи.