luogu#P1502. 窗口的星星

窗口的星星

题目背景

小卡买到了一套新房子,他十分的高兴,在房间里转来转去。

题目描述

晚上,小卡从阳台望出去,“哇~~~~好多星星啊”,但他还没给其他房间设一个窗户。

天真的小卡总是希望能够在晚上能看到最多最亮的星星,但是窗子的大小是固定的,边也必须和地面平行。

这时小卡使用了超能力(透视术)知道了墙后面每个星星的位置和亮度,但是小卡发动超能力后就很疲劳,只好拜托你告诉他最多能够有总和多亮的星星能出现在窗口上。

输入格式

本题有多组数据,第一行为 TT,表示有 TT 组数据。

对于每组数据:

第一行 33 个整数 n,W,Hn,W,H 表示有 nn 颗星星,窗口宽为 WW,高为 HH

接下来 nn 行,每行三个整数 xi,yi,lix_i,y_i,l_i 表示星星的坐标在 (xi,yi)(x_i,y_i),亮度为 lil_i

输出格式

TT 个整数,表示每组数据中窗口星星亮度总和的最大值。

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

提示

为了便于理解,输入样例中每组数据之间添加了空行,实际测试数据中并无空行。

小卡买的窗户框是金属做的,所以在边框上的不算在内。

数据范围

对于 100%100\% 的数据:1T101\le T \le 101n1041\le n \le 10^41W,H1061\le W,H \le 10^60xi,yi<2310\le x_i,y_i < 2^{31}