P16896 [GKS 2022 #G] Cute Little Butterfly

在魔法世界的一片森林里，有一个充满神奇生物的花园。花园里有许多花朵，它们不仅美丽，还是蝴蝶的能量来源。 将花园视为一个二维平面，其中 $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$ 是我们可爱的小蝴蝶能获得的最大总能量。

在测试用例 #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 完成