题目描述

在魔法世界的一片森林里，有一个充满神奇生物的花园。花园里有许多花朵，它们不仅美丽，还是蝴蝶的能量来源。

将花园视为一个二维平面，其中 $X$ 轴代表地面，$Y$ 轴代表海拔高度。在 $X$ 轴上每个非负整数点处都有无限高的植物。花园里有 $N$ 朵花，第 $i$ 朵花位于点 $(X_i, Y_i)$，带有能量值为 $C_i$ 的花蜜。

我们可爱的小蝴蝶希望获得尽可能多的能量来变得强大。通过移动到花朵的同一位置，蝴蝶可以消耗其花蜜并获得该花朵的能量值。每朵花的花蜜只能被消耗一次。

蝴蝶初始位于点 $(0, 10^{18})$，拥有 $0$ 单位能量，面朝右侧。在任何时刻，蝴蝶可以：

• 移动到更低的海拔，即从 $(x, y)$ 到 $(x, y - 1)$，仅当当前海拔为正 $(y > 0)$ 时。
• 沿 $X$ 轴正方向移动，即从 $(x, y)$ 到 $(x + 1, y)$，如果它面朝右侧。
• 沿 $X$ 轴负方向移动，即从 $(x, y)$ 到 $(x - 1, y)$，如果它面朝左侧。
• 改变它面朝的方向（从左到右或反之）。这将消耗 $E$ 单位能量。

我们知道我们的蝴蝶很懒，讨厌在旅程中向上移动。因此，在本问题中，我们假设不允许向上移动。此外，能量在任何时候都可以为负值。负能量意味着蝴蝶消耗的能量超过了它从花朵中获得的能量。

求我们可爱的小蝴蝶能获得的最大能量。

输入格式

输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。

每个测试用例的第一行包含两个整数 $N$ 和 $E$：花朵的数量以及每次转向所需的能量。

接下来的 $N$ 行描述花朵。第 $i$ 行包含三个整数 $X_i$、$Y_i$ 和 $C_i$：第 $i$ 朵花的位置和能量值。

输出格式

对于每个测试用例，输出一行，格式为 Case #x: y，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是我们可爱的小蝴蝶能获得的最大总能量。

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

提示

在测试用例 #1 中，有 $N = 4$ 朵花，$E = 10$。为了最大化总能量，蝴蝶可以这样移动：

:::align{center} :::

• 从第二朵花收集能量。当前总能量为 $2$ 单位。
• 向右移动，从第四朵花收集能量。当前总能量为 $4$ 单位。
• 向下移动，从第三朵花收集能量。当前总能量为 $6$ 单位。

因此，蝴蝶以此方式获得的总能量为 $6$ 单位。

在测试用例 #2 中，有 $N = 6$ 朵花，$E = 5$。为了最大化总能量，蝴蝶可以这样移动：

:::align{center} :::

• 从第三朵花收集能量。当前总能量为 $5$ 单位。
• 向右和向下移动，从第四朵花收集能量。当前总能量为 $7$ 单位。
• 向右和向下移动，从第五朵花收集能量。当前总能量为 $8$ 单位。
• 改变方向为向左。当前总能量为 $3$ 单位。
• 向左移动，从第六朵花收集能量。当前总能量为 $13$ 单位。
• 向左和向下移动，从第一朵花收集能量。当前总能量为 $17$ 单位。

因此，蝴蝶以此方式获得的总能量为 $17$ 单位。

限制条件

$1 \le T \le 100$。

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

对于所有 $i$，$1 \le C_i \le 10^9$。

所有花朵位于不同的点。

测试集 1

$1 \le N \le 6$。

对于所有 $i$，$0 \le X_i \le 500$。

对于所有 $i$，$0 \le Y_i \le 500$。

测试集 2

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

对于所有 $i$，$0 \le X_i \le 500$。

对于所有 $i$，$0 \le Y_i \le 500$。

测试集 3

对于所有 $i$，$0 \le X_i \le 10^5$。

对于所有 $i$，$0 \le Y_i \le 10^9$。

最多 $10$ 个测试用例满足：

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

其余测试用例满足：

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

翻译由 DeepSeek V4 Pro 完成