Cow Meetings

There are two barns on a one-dimensional number line located at points \(0\) and \(L\) (with \(1 \le L \le 10^9\)). There are \(N\) cows (\(1 \le N \le 5 \times 10^4\)), each at a distinct position \(x_i\) and having a weight between \(1\) and \(10^3\). Each cow \(i\) moves at a speed of one unit per second, with its initial direction given by \(d_i\) (either \(1\) for the positive direction or \(-1\) for the negative direction). Both cows and barns are considered points.

The cows follow these rules:

• If cow \(i\) reaches a barn (i.e. position \(0\) or \(L\)), it stops moving.
• If two cows \(i\) and \(j\) meet at a point that is not a barn, they immediately exchange velocities. (Note: Because cows exchange speeds when meeting, it can be shown that their motion is equivalent to them passing through each other without changing speeds, though their identities are exchanged.)

Let \(T\) be the earliest time such that the sum of the weights of the cows which have stopped (i.e. reached a barn) is at least half of the total weight of all cows. In other words, if \(W_{total}\) is the total weight, then \(T\) is the minimum time at which the stopped cows have total weight \(\geq \lceil W_{total}/2 \rceil\).

Your task is to determine the total number of meetings (collisions) between pairs of cows that occur during the time interval \([0, T]\), inclusive.

Hint: Due to the exchange of velocities upon meeting, the cows' motion is equivalent to them continuing along their initial path (``ghost'' cows). A pair of cows, one moving right and the other moving left, will meet at time \(\frac{x_j - x_i}{2}\) if they start at positions \(x_i < x_j\). Count such pairs with \(\frac{x_j - x_i}{2} \le T\). Also, note that the identity of the cows that reach the barns (and hence the time \(T\)) can be determined by ordering the cows by position and simulating barn exits from the two ends. For a cow with ghost exit, the exit time is:

• If moving left: \(x_i\).
• If moving right: \(L - x_i\).

One can simulate exit events by processing cows in increasing order (for the left barn) and in decreasing order (for the right barn) until the cumulative weight of cows that have exited reaches at least \(\lceil W_{total}/2 \rceil\). Let \(T\) be the exit time of the last cow that makes the cumulative weight reach this threshold.

inputFormat

The first line contains two integers \(N\) and \(L\): the number of cows and the position of the right barn. The next \(N\) lines each contain three integers \(x_i\), \(w_i\) and \(d_i\), representing the initial position, weight, and direction of the cow. It is guaranteed that the \(x_i\)'s are distinct and \(d_i\) is either \(1\) (moving right) or \(-1\) (moving left).

outputFormat

Output a single integer — the total number of meetings between cows that occur during the time interval \([0, T]\), inclusive.

sample

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

2