Description

At night, Xiao Ka looks out from the balcony and exclaims, “Wow, so many stars!”, but he has not yet set a window for the other rooms.

Naive as he is, Xiao Ka always hopes to see the most and brightest stars at night, but the window’s size is fixed and its sides must be parallel to the ground. He uses a superpower (clairvoyance) to learn the position and brightness of every star behind the wall. However, using the superpower makes him tired, so he asks you to tell him the maximum possible total brightness of stars that can appear in the window.

Input Format

This problem has multiple test cases. The first line is $T$, indicating there are $T$ test cases.

For each test case:

• The first line has $3$ integers $n, W, H$, meaning there are $n$ stars, and the window has width $W$ and height $H$.
• The next $n$ lines each contain three integers $x_i, y_i, l_i$, meaning there is a star at coordinate $(x_i, y_i)$ with brightness $l_i$.

Output Format

Output $T$ integers, each being the maximum total brightness of stars that can appear in the window for the corresponding test case.

2

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

Hint

For ease of understanding, blank lines are added between test cases in the sample input, but the actual testdata contains no blank lines.

The window frame is made of metal, so stars on the boundary do not count.

Constraints: For $100\%$ of the testdata: $1 \le T \le 10$, $1 \le n \le 10^4$, $1 \le W, H \le 10^6$, $0 \le l_i \le 1000$, $0 \le x_i, y_i < 2^{31}$.

Translated by ChatGPT 5