题目描述

众所周知,想要制作好吃的炒饭,一口好的中华锅和各种各样的材料是必不可少的,最常见的材料有河之主、幻之山菜、涌泉水、野猪王。在夏日的每一天,umi都会用当天在鸟白岛上收集到的材料制作一份炒饭并给炒饭打分。
DQAUFs.png
今天,umi照例出门在鸟白岛上寻找制作炒饭的材料了。现在在鸟白岛上有n个制作炒饭的材料,材料之间互不冲突。第i个材料位于$(x_i,y_i)$上,并且有一个美味值$v_i$。但是由于umi的时间有限,她只能选择一个长为w,宽为h的矩形区域(假设矩形区域的左下角为$(x_0,y_0)$,那么这个矩形区域的右上角就是$(x_0 + w,y_0 + h)$,并且矩形区域不可以被旋转),收集这个矩形区域内所有的材料,并在回去之后用这些材料制作炒饭。(在矩形边上的材料也会被收集)最后制作出来的炒饭的评分是这些收集到的美味值之和。那么你能告诉umi,她制作出来的炒饭最高能有多少分吗?


输入格式

第一行包括三个整数$n,w,h(n \leq 10^4,1\leq w, h \leq 2\times 10^4)$,分别表示鸟白岛上制作炒饭的材料的数目、umi选择矩形区域的长、umi选择的矩形区域的宽。

接下来有n行,第i行有三个整数$x,y,v_i(-10^4 \leq x,y\leq 10^4,1\leq w\leq 10^5)$,分别表示第i种材料的x坐标、y坐标、美味值。


输出格式

输出一行一个整数,表示umi做出炒饭可以达到的最高分。


样例数据

输入

3 2 1
-2 0 2
0 1 2
1 3 3

输出

4

备注

样例中选择的是以(-2,0)为左下角,(0,1)为右上角的矩形区域,矩形区域中的美味值之和为4。


信息

时间限制: 1s
内存限制: 128MB
评测模式: Normal

导航

比赛介绍
比赛排名
数据统计
评测状态
答疑平台
打印服务