Problem Description

In a forest of the magical world, there lies a garden full of magical creatures. The garden has plenty of flowers which are not just beautiful but also a source of energy for butterflies.

Consider the garden a $2$D plane where the $X$-axis represents the ground, and the $Y$-axis represents the altitude. There are plants of infinite height on every non-negative integral point on the $X$-axis. There are $N$ flowers in the garden, where the $i$-th flower is on the point $(X_i, Y_i)$ with the nectar of some energy value $C_i$.

Our cute little butterfly wants as much energy as possible to become strong. By going to the same position of a flower, the butterfly can consume its nectar and gain that flower's energy value. Each flower's nectar can only be consumed once.

The butterfly is initially at point $(0, 10^{18})$ with $0$ units of energy and facing towards the right. At any point, the butterfly can:

• Move to a lower altitude, that is, from $(x, y)$ to $(x, y - 1)$ only if its current altitude is positive $(y > 0)$.
• Move in the positive direction along the $X$-axis, that is, from $(x, y)$ to $(x + 1, y)$ if it is facing right.
• Move in the negative direction along the $X$-axis, that is, from $(x, y)$ to $(x - 1, y)$ if it is facing left.
• Change the direction it is facing (from left to right or vice versa). This will consume $E$ units of energy.

We know our butterfly is lazy, and it hates to move upwards during the journey. So, for this problem, we will assume that going upwards is not allowed. Also, energy can be negative at any point. Negative energy means the butterfly has spent more energy than it obtained from the flowers.

Find the maximum energy our cute butterfly can achieve.

Input Format

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

The first line of each test case contains two integers, $N$ and $E$: the number of flowers and the energy required per turn, respectively.

The next $N$ lines describe the flowers. The $i$-th line contains three integers, $X_i$, $Y_i$ and $C_i$: the position and the energy value of the $i$-th flower, respectively.

Output Format

For each test case, output one line containing Case #$x$: $y$, where $x$ is the test case number (starting from $1$) and $y$ is the maximum overall energy our cute butterfly can achieve.

2
4 10
1 1 2
1 2 2
2 1 2
2 2 2
6 5
1 1 4
1 3 1
3 4 5
4 3 2
5 2 1
3 2 10

Case #1: 6
Case #2: 17

Hint

In sample test case #$1$, there are $N = 4$ flowers and $E = 10$. To maximise the overall energy our butterfly can move in this way:

:::align{center} :::

• Collect energy from the second flower. Total energy is now $2$ units
• Collect energy from the fourth flower, by moving right. Total energy is now $4$ units
• Collect energy from the third flower, by moving down. Total energy is now $6$ units

Hence, the total energy the butterfly got in this way is $6$ units.

In sample test case # $2$, there are $N = 6$ flowers and $E = 5$. To maximise the overall energy our butterfly can move in this way:

:::align{center} :::

• Collect energy from the third flower. Total energy is now $5$ units
• Collect energy from the fourth flower, by moving right and down. Total energy is now $7$ units
• Collect energy from the fifth flower, by moving right and down. Total energy is now $8$ units
• Change direction to left. Total energy is now $3$ units
• Collect energy from the sixth flower, by moving left. Total energy is now $13$ units
• Collect energy from the first flower, by moving left and down. Total energy is now $17$ units

Hence, the total energy the butterfly got in this way is $17$ units.

Limits

$1 \le T \le 100$.

$0 \le E \le 10^9$.

$1 \le C_i \le 10^9$, for all $i$.

All flowers are located at distinct points.

Test Set 1

$1 \le N \le 6$.

$0 \le X_i \le 500$, for all $i$.

$0 \le Y_i \le 500$, for all $i$.

Test Set 2

$1 \le N \le 10^3$.

$0 \le X_i \le 500$, for all $i$.

$0 \le Y_i \le 500$, for all $i$.

Test Set 3

$0 \le X_i \le 10^5$, for all $i$.

$0 \le Y_i \le 10^9$, for all $i$.

For at most $10$ cases:

$1 \le N \le 10^5$.

For the remaining cases:

$1 \le N \le 10^4$.