Görüşlər
İki tövlə 0-dan l-ə qədər olan ədədi oxda yerləşir. n inək bu ədədi oxda müxtəlif yerlərdə yerləşir (tövlələr və inəklər nöqtələr kimi qəbul edilir). Hər bir inək i əvvəlcə müəyyən bir mövqedə x[i] yerləşir və müsbət və ya mənfi istiqamətdə saniyədə bir vahid sürətlə hərəkət edir, bu da ya 1, ya da -1 olan tam ədəd d[i] ilə təmsil olunur. Hər bir inəyin çəkisi də w[i] [1, 10^3] aralığında olur. Bütün inəklər sabit sürətlə hərəkət edir, ta ki aşağıdakı hadisələrdən biri baş verənə qədər:
Əgər inək i tövləyə çatarsa, o dayanır.
Görüş, iki inək i və j eyni nöqtədə olduqda baş verir, bu nöqtə tövlə deyil. Bu halda, inək i-yə inək j-nin əvvəlki sürəti təyin edilir və əksinə. Qeyd edək ki, inəklər tam ədəd olmayan nöqtələrdə də görüşə bilərlər.
t ən erkən vaxt anı olsun ki, hərəkət etməyi dayandıran inəklərin çəkilərinin cəmi (onlar tövlələrdən birinə çatdıqları üçün) bütün inəklərin çəkilərinin cəminin ən azı yarısını təşkil edir. 0 ... t (vaxt t daxil olmaqla) zaman aralığında inəklər arasında baş verən görüşlərin ümumi sayını müəyyən edin.
Giriş Məlumatları
Birinci sətir iki tam ədəd n (1 ≤ n ≤ 5 * 10^4) və l (1 ≤ l ≤ 10^9) ehtiva edir. Növbəti n sətir hər biri üç tam ədəd w[i], x[i] və d[i] ehtiva edir. Bütün mövqelər x[i] fərqlidir və 0 < x[i] < l bərabərsizliyini təmin edir.
Çıxış Məlumatları
Cavabı ehtiva edən bir sətir çıxarın.
Nümunə
Bu nümunədə inəklər aşağıdakı kimi hərəkət edir:
Birinci və ikinci inəklər 0.5 vaxt anında 1.5 nöqtəsində görüşürlər. Birinci inəyin sürəti indi -1, ikinci inəyin sürəti isə 1 olur.
İkinci və üçüncü inəklər 1 vaxt anında 2 nöqtəsində görüşürlər. İkinci inəyin sürəti indi -1, üçüncü inəyin sürəti isə 1 olur.
Birinci inək 2 vaxt anında sol tövləyə çatır.
İkinci inək 3 vaxt anında sol tövləyə çatır.
İndi proses bitir, çünki tövləyə çatan inəklərin çəkilərinin cəmi bütün inəklərin çəkilərinin ən azı yarısını təşkil edir. Üçüncü inək 4 vaxt anında sağ tövləyə çatacaq.
Dəqiq iki görüş baş verdi.