题目描述

北海上散落着 $N$ 件垃圾，编号为 $1,2,\ldots,N$。第 $i$ 件垃圾位于坐标 $(x_i,y_i)$，重量为 $w_i$。

现在要进行一次清理行动：所有位于某个矩形区域内的垃圾都会被收集。这个矩形区域的宽为 $W$，高为 $H$，但它的具体位置尚未确定。

请你确定：如果可以任意放置这个清理矩形，最多能够收集到多少总重量的垃圾。

矩形边界上的垃圾也视为在矩形内。

输入格式

第一行包含三个整数：

N W H

接下来 $N$ 行，第 $i$ 行包含三个整数：

x_i y_i w_i

表示第 $i$ 件垃圾的位置和重量。

输出格式

输出一个整数，表示能够收集到的垃圾最大总重量。

数据范围

• $1 \le N \le 10^5$。
• $1 \le W,H \le 10^9$。
• 对所有 $1 \le i \le N$，有 $0 \le x_i,y_i < 10^9$。
• 对所有 $1 \le i \le N$，有 $1 \le w_i \le 10^9$。

子任务

1. $10$ 分：$N \le 400$。
2. $12$ 分：对所有 $1 \le i \le N$，$W,H,x_i,y_i < 2000$。
3. $15$ 分：$N \le 2000$。
4. $22$ 分：$H = 10^9$。
5. $23$ 分：对所有 $1 \le i \le N$，$W,H,x_i,y_i < 10^5$。
6. $18$ 分：无额外限制。

样例

输入

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)$ 处的三件垃圾，总重量为：