#P4469. [Jsoi2013]打地鼠

    ID: 3703 传统题 1000ms 512MiB 尝试: 71 已通过: 20 难度: 8 上传者: 标签>难度分类提高+/省选-构造与建模对称性分析图论拆点限制点容量指定流量最小费用流动态规划DAG 动态规划势能优化费用流Dijkstra残量增广路CF2500By

[Jsoi2013]打地鼠

[JSOI2013] 打地鼠

题目描述

打地鼠游戏发生在一条直线上。第 ii 只地鼠在时刻 TiT_i 瞬间出现在位置 XiX_i,随即消失。若在该时刻有一只手恰好位于 XiX_i,JYY 可以击中这只地鼠并获得 PiP_i 分。

时刻 00,JYY 的左手在位置 XleftX_{\mathrm{left}},右手在位置 XrightX_{\mathrm{right}}。每只手的最大移动速度为 VV,两只手可以同时移动,也可以在同一时刻各打一只地鼠。在整个游戏过程中,左手的位置必须严格小于右手的位置。

请计算 JYY 最多能获得多少分。

输入格式

第一行输入四个整数 N,V,Xleft,XrightN,V,X_{\mathrm{left}},X_{\mathrm{right}}。

接下来 NN 行,每行输入三个整数 Xi,Ti,PiX_i,T_i,P_i,描述一只地鼠。保证同一时刻的地鼠出现在不同位置。

输出格式

输出一行一个整数,表示可以获得的最高分数。

样例

3 10 150 250
100 20 123
201 10 67
202 10 45
190

样例说明

左手可在前 1010 个时间单位内从 150150 移到 100100 并等到时刻 2020,获得 123123 分。同时,右手在时刻 1010 到达位置 201201,获得 6767 分。两只手始终保持严格的左右顺序,总分为 190190。

数据范围

1≤N≤30001\le N\le 3000,1≤V≤1041\le V\le 10^4,1≤Xleft<Xright≤1051\le X_{\mathrm{left}}<X_{\mathrm{right}}\le 10^5,1≤Xi,Ti,Pi≤1051\le X_i,T_i,P_i\le 10^5。