Hai trang trại nằm trên vị trí ~0~ và ~L (1 \leq L \leq 10^9)~ trên trục số. Có ~N~ con bò ~(1 \leq L \leq 5*10^4)~ nằm trên các vị trí phân biệt trên trục số này. Ban đầu, con bò thứ i nằm ở vị trí ~x_i~ và di chuyển theo chiều dương hoặc âm với vận tốc 1 đơn vị 1 giây, được thể hiện bằng số nguyên ~d_i~ có giá trị bằng ~1~ hoặc ~-1~. Mỗi con bò cũng có cân nặng ~w_i~ trong khoảng ~[1,10^3]~. Mỗi con bò di chuyển với vận tốc không đổi cho đến một trong những việc sau diễn ra:
Nếu con bò thứ ~i~ tới được trang trại, thì con bò thứ ~i~ dừng di chuyển.
Một cuộc va chạm gặp diễn ra khi 2 con bò ~i~ và ~j~ chiếm cùng mỗi điểm, điểm đó không phải trang trại. Trong trường hợp nó, bò ~i~ sẽ được gán vận tốc của bò ~j~ và ngược lại. Lưu ý rằng những con bò có thể gặp tại điểm không nguyên.
Gọi ~T~ là thời điểm sớm nhất mà tổng khối lượng của những con bò đã dừng (do đã tới trang trại) bằng ít nhất một nửa tổng khối lượng của những con bò. Hãy xác định tổng số va chạm trong khoảng thời gian ~0…T~ (tính cả ~T~).
Input
Dòng đầu tiên chứa ~2~ số nguyên ~N~ và ~L~, cách bởi ~1~ dấu cách.
~N~ dòng tiếp theo, dòng thứ ~i~ chứa 3 số nguyên ~w_i~, ~x_i~, và ~d_i~. Mọi ~x_i~ đều phân biệt và thỏa mãn ~ 0 \lt x_i \lt L~
Output
In ra số lượng va chạm.
Sample Input
3 5
1 1 1
2 2 -1
3 3 -1
Sample Output
2
Giải thích
Những con bò di chuyển theo các bước sau:
- Bò thứ nhất và thứ hai gặp nhau tại vị trí 1.5 vào thời điểm 0.5. Bò thứ nhất hiện có vận tốc là −1 và bò thứ hai có vận tốc là 1.
- Bò thứ hai và bò thứ ba gặp nhau gặp nhau tại vị trí thứ 2 vào thời điểm 1. Bò thứ hai hiện có vận tốc là −1 và bò thứ ba có vận tốc là 1.
- Bò thứ nhất sẽ tới được trang trại bên trái vào thời điểm 2.
- Bò thứ hai tới được trang trại bên trái vào thời điểm 3.
- Quá trình kết thúc do tổng khối lượng của bò đã tới trang trại đã bằng ít nhất một nửa tổng khối lượng tất cả các con bò. Tổng cộng đã có 2 va chạm.
Subtask
- Test 1 là test ví dụ
- Test 2-4 có giới hạn ~N \le 10^2~ và ~w_i=1~ với mọi ~i~
- Test 5-7 có giới hạn ~N \le 10^2~ và ~w_i=1~ với mọi ~i~
- Các test còn lại không có giới hạn gì thêm.
Comments