Between Two Cameras

In a rectangular room there are $N$ sleeping cats. Each cat has a position on the floor and a weight. They do not move.

Two cameras are located at adjacent corners of the room. Each camera starts pointing toward the other camera and turns $90^\circ$ toward the interior of the room. As it turns, it records each cat when it points directly at that cat. Each camera then creates a panoramic image showing the cats in the order it recorded them.

A control system compares the two panoramas. A pair of distinct cats $\{A,B\}$ is flagged if $A$ appears before $B$ in one panorama and after $B$ in the other. Each flagged pair needs manual review, at a cost equal to the product of the weights of those two cats.

Given the positions and weights of the cats, you must find the sum of the costs of all flagged pairs.

Input

The first line contains two integers $N$ ($2 \le N \le 2 \times 10^{5}$) and $D$ ($2 \le D \le 10^{9}$), indicating respectively the number of cats and the distance between the two cameras.

The floor is represented in the plane, with the cameras located at $(0,0)$ and $(D,0)$. The interior of the room is on the side where the second coordinate is positive.

Each of the next $N$ lines describes a cat with three integers $X$ ($1 \le X \le D-1$), $Y$ ($1 \le Y \le 10^{9}$) and $W$ ($1 \le W \le 10^{4}$), where $(X,Y)$ is the position of the cat and $W$ is its weight.

It is guaranteed that neither camera ever points directly at two cats at once.

Output

Output a single line with an integer indicating the sum of the costs of all flagged pairs.

3 10
5 2 3
5 3 4
5 1 2

0

3 10
5 3 2
8 3 3
2 3 1

11

5 12
6 5 5
2 6 2
10 7 1
4 2 3
8 3 4

37