Hai chuồng bò nằm tại các vị trí \(0\) và \(L\) (\(1 \leq L \leq 10^9\)) trên một trục số một chiều. Ngoài ra còn có \(N\) cô bò (\(1 \leq N \leq 5\cdot 10^4\)) ở các vị trí phân biệt trên trục số này (có thể coi các chuồng bò và các cô bò là những điểm). Ban đầu, mỗi bò \(i\) nằm tại một vị trí \(x_i\) và di chuyển theo chiều dương hoặc chiều âm với vận tốc một đơn vị mỗi giây, được biểu diễn bởi một số nguyên \(d_i\) bằng \(1\) hoặc \(-1\). Mỗi cô bò còn có trọng lượng \(w_i\) thuộc phạm vi \([1,10^3]\). Tất cả các cô bò luôn di chuyển với vận tốc không đổi cho đến khi xảy ra một trong những sự kiện sau:

• Nếu bò \(i\) đến một chuồng bò thì bò \(i\) dừng di chuyển.
• Một cuộc gặp xảy ra khi hai bò \(i\) và \(j\) cùng ở một điểm, trong đó điểm này không phải là chuồng bò. Khi đó, bò \(i\) nhận vận tốc trước đó của bò \(j\) và ngược lại. Lưu ý rằng các cô bò có thể gặp nhau tại những điểm không nguyên.

Gọi \(T\) là thời điểm sớm nhất mà tổng trọng lượng của những cô bò đã dừng di chuyển (do đến một trong hai chuồng) ít nhất bằng một nửa tổng trọng lượng của tất cả các cô bò. Hãy xác định tổng số cuộc gặp giữa các cặp bò trong khoảng thời gian \(0 \ldots T\) (kể cả tại thời điểm \(T\)).

Phân nhóm

• Các test 2–4 thỏa mãn \(N \leq 10^2\) và \(w_i=1\) với mọi \(i\).
• Các test 5–7 thỏa mãn \(N \leq 10^2\).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(L\), cách nhau bởi dấu cách.

Mỗi dòng trong \(N\) dòng tiếp theo chứa ba số nguyên \(w_i\), \(x_i\) và \(d_i\), cách nhau bởi dấu cách. Tất cả các vị trí \(x_i\) đều phân biệt và thỏa mãn \(0<x_i<L\).

Dữ liệu ra

In một dòng duy nhất chứa đáp án.

Ví dụ

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

2

Nguồn

USACO 2019 December Contest, Silver - Meetings: https://usaco.org/index.php?page=viewproblem2&cpid=967

Tác giả: Benjamin Qi.