Jump

There are $N$ tiles on a two-dimensional plane. Tile $i$ sits at $(x_i, y_i)$ and carries one energy bottle that refills your jumping energy by $e_i$.

You jump to the right or up, and nowhere else. A jump from tile $(x_1, y_1)$ to tile $(x_2, y_2)$ is allowed when $y_1 = y_2$ and $x_1 < x_2$ (to the right), or when $x_1 = x_2$ and $y_1 < y_2$ (up). The two tiles do not have to be adjacent. Any tile that lies in that direction on the same row or the same column is a legal landing spot. You cannot jump to a place with no tile.

Every jump costs $B$ energy. You cannot jump while your energy is smaller than $B$. The moment you land on a new tile you take its energy bottle and your energy grows by $e_i$.

You start on tile $1$ with energy $e_1$. Jump from tile $1$ to tile $N$ so that the energy left when you arrive at tile $N$ is as large as possible.

Write a program that finds that maximum energy.

The first line contains the number of test cases $T$. ($1 \le T \le 10$)

The first line of each test case contains two integers $N$ and $B$. ($2 \le N \le 300000$, $1 \le B \le 1000$)

The next $N$ lines describe tile $1$ through tile $N$ in order. Each line contains three integers $x_i$, $y_i$, $e_i$. ($0 \le x_i, y_i \le 100000$, $0 \le e_i \le 1000$)

No two tiles share a coordinate. At least one sequence of jumps from tile $1$ to tile $N$ obeys the energy rule.

For each test case, print on one line the maximum energy you can hold when you arrive at tile $N$.