#216881. [GKS 2022 #G] Cute Little Butterfly

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 D plane where the -axis represents the ground, and the -axis represents the altitude. There are plants of infinite height on every non-negative integral point on the -axis. There are flowers in the garden, where the -th flower is on the point with the nectar of some energy value .

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 with units of energy and facing towards the right. At any point, the butterfly can:

• Move to a lower altitude, that is, from to only if its current altitude is positive .
• Move in the positive direction along the -axis, that is, from to if it is facing right.
• Move in the negative direction along the -axis, that is, from to if it is facing left.
• Change the direction it is facing (from left to right or vice versa). This will consume 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.

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

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

The next lines describe the flowers. The -th line contains three integers, , and : the position and the energy value of the -th flower, respectively.

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

样例输入 1

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

样例输出 1

Case #1: 6
Case #2: 17

In sample test case #, there are flowers and . To maximise the overall energy our butterfly can move in this way:

:::align{center} :::

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

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

In sample test case # , there are flowers and . To maximise the overall energy our butterfly can move in this way:

:::align{center} :::

• Collect energy from the third flower. Total energy is now units
• Collect energy from the fourth flower, by moving right and down. Total energy is now units
• Collect energy from the fifth flower, by moving right and down. Total energy is now units
• Change direction to left. Total energy is now units
• Collect energy from the sixth flower, by moving left. Total energy is now units
• Collect energy from the first flower, by moving left and down. Total energy is now units

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

Limits

.

.

, for all .

All flowers are located at distinct points.

Test Set 1

.

, for all .

, for all .

Test Set 2

.

, for all .

, for all .

Test Set 3

, for all .

, for all .

For at most cases:

.

For the remaining cases:

.