[AdditionalFile4842.zip](file://AdditionalFile4842.zip?type=additional_file)

#4842. 「NordicOI 2025」Garbage Collection

标签: 传统 | 时间限制: 5000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 NordicOI 2025 T2 「Garbage Collection」

北海上漂浮着 $N$ 块垃圾，编号从 $1$ 到 $N$。第 $i$ 块垃圾位于坐标 $\left(x_{i}, y_{i}\right)$，重量为 $w_{i}$。作为一项清理行动的一部分，你需要在某个矩形区域内收集所有垃圾。这个矩形区域的宽度为 $W$，高度为 $H$，但具体位置尚未确定。

你的任务是确定在最佳位置放置清理区域时，能够收集到的垃圾总重量的最大值。

输入格式

第一行包含三个整数 $N, W$ 和 $H$。

接下来的 $N$ 行中，第 $i$ 行包含三个整数 $x_{i}, y_{i}$ 和 $w_{i}$，分别表示第 $i$ 块垃圾的坐标和重量。

输出格式

你的程序需要输出一个整数：通过最佳放置清理区域，能够收集到的垃圾总重量的最大值。

样例

输入

5 3 2
3 1 10
2 1 5
1 0 5
0 2 10
1 3 5

输出

20

最佳的清理区域应覆盖坐标为 $(3,1)$、$(2,1)$ 和 $(1,0)$ 的垃圾，总重量为 $10+5+5=20$。

数据范围与提示

对于所有数据，满足：

• $1 \leq N \leq 10^{5}$
• $1 \leq W, H \leq 10^{9}$
• $0 \leq x_{i}, y_{i} < 10^{9}$（对于所有 $1 \leq i \leq N$）
• $1 \leq w_{i} \leq 10^{9}$（对于所有 $1 \leq i \leq N$）

详细子任务附加限制及分值如下表所示：