Description

[POJ 2482]

在一个天空中有很多星星（看作平面直角坐标系），已知每颗星星的坐标和亮度（都是整数）。

求用宽为W、高为H的矩形窗户（W,H为正整数）能圈住的星星的亮度总和最大是多少。（矩形边界上的星星不算）

Input Format

输入包含多组测试用例。

每个用例的第一行包含3个整数：n，W，H，表示星星的数量，矩形窗口的宽和高。

然后是n行，每行有3个整数：x，y，c，表示每个星星的位置（x，y）和亮度。

没有两颗星星在同一点上。

数据范围

1 ≤ n ≤ 10000,

1 ≤ W,H ≤ 1000000,

$0 ≤ x,y < 2^{31}$

Output Format

每个测试用例输出一个亮度总和最大值。

每个结果占一行。

3 5 4
1 2 3
2 3 2
6 3 1
3 5 4
1 2 3
2 3 2
5 3 1​

5
6​

Source

线段树 扫描线