garbage — NOINordic contest
Task type: batch | Time limit: 5 s | Memory limit: 1024 MB | Difficulty: 20
Algorithms: line sweep, segment tree, coordinate compression

# Garbage Collection

The north sea is littered with *N* pieces of garbage, numbered 1 to *N*. The *i*-th piece is at position (*x<sub>i</sub>*, *y<sub>i</sub>*) and has a weight of *w<sub>i</sub>*. As part of a cleanup effort, all garbage within a rectangular area will be collected. This area has a width of *W* and a height of *H*, but its location has not yet been decided.

Determine the maximum total weight of garbage that will be collected if the cleanup area is positioned optimally.

## Input

The first line contains the integers *N*, *W*, and *H*.

The *i*-th of the next *N* lines contains the integers *x<sub>i</sub>*, *y<sub>i</sub>*, and *w<sub>i</sub>*.

## Output

Your program should output a single integer: the maximum total weight of garbage that can be collected.

## Constraints

*   1 ≤ *N* ≤ 10<sup>5</sup>.
*   1 ≤ *W*, *H* ≤ 10<sup>9</sup>.
*   0 ≤ *x<sub>i</sub>*, *y<sub>i</sub>* < 10<sup>9</sup> for all *i*: 1 ≤ *i* ≤ *N*.
*   1 ≤ *w<sub>i</sub>* ≤ 10<sup>9</sup> for all *i*: 1 ≤ *i* ≤ *N*.

## Subtasks

*   1\. (10 points) *N* ≤ 400.
*   2\. (12 points) *W*, *H*, *x<sub>i</sub>*, *y<sub>i</sub>* < 2000 for all *i*: 1 ≤ *i* ≤ *N*.
*   3\. (15 points) *N* ≤ 2000.
*   4\. (22 points) *H* = 10<sup>9</sup>.
*   5\. (23 points) *W*, *H*, *x<sub>i</sub>*, *y<sub>i</sub>* < 10<sup>5</sup> for all *i*: 1 ≤ *i* ≤ *N*.
*   6\. (18 points) No additional constraints.

## Example

**Input:**

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

**Output:**

```
20

Starter code: