2154. Firework 1007

kkz\text{kkz} 好好读书的时候,crq\text{crq} 溜出去看烟花了!

crq\text{crq} 在一条烟花街道上,烟花街道有 nn 个烟花燃放点,分别按 1n1 \sim n 标号,标号相邻燃放点之间距离 11 单位距离。

将会有 mm 束烟花在街道上燃放,同时同地只会燃放至多一束烟花

已知每个烟花的燃放点 aia_i、烟花的精彩值 bib_i、烟花的颜色 cic_i、燃放时间 tit_i

如果 tit_i 时,crq\text{crq} 位于燃放点 aia_i,则可以选择观看第 ii 束烟花。

最初 crq\text{crq} 的快乐值为 00,在观看第 ii 束烟花后 crq\text{crq} 的快乐值会发生下面的变化:

  • crq\text{crq} 的快乐值增加 bib_i

  • ci=1c_i=1crq\text{crq} 的快乐值变为原来的相反数。

假设初始时间 t=0t=0,初始时 crq\text{crq} 的位置任选,每 11 单位时间 crq\text{crq} 可以移动至多 kk 单位距离,求在所有烟花燃放结束后,crq\text{crq} 快乐值的最大值。

输入

第一行包含三个整数 n,m,kn,m,k,分别表示烟花燃放点总数、烟花总数和 crq\text{crq} 的移动速度。

接下来 mm 行每行包含 44 个整数,分别表示 ai,bi,ci,tia_i,b_i,c_i,t_i

输出

输出一行一个整数,表示在所有烟花燃放结束后,crq\text{crq} 快乐值的最大值。

样例

标准输入 复制文本
5 6 3
1 1 0 2
1 -9 1 4
4 -1 0 4
5 9 1 3
1 8 0 5
4 10 1 3
标准输出 复制文本
28
标准输入 复制文本
2 3 1
1 -5 0 5
2 -4 1 2
2 4 1 3
标准输出 复制文本
4
标准输入 复制文本
2 6 2
2 1 0 2
2 -5 0 10
1 -1 1 9
1 -1 1 8
2 8 0 5
1 -2 0 3
标准输出 复制文本
9

提示

【样例解释 #1】

tt位置快乐值
111100
221111
334411-11
44112020
55112828

【数据范围】

对于所有的测试数据,保证 1ain109,1m5×105,1ti,k109,109bi109,0ci11 \leq a_i \leq n \leq 10^9,1 \leq m \leq 5 \times 10^5,1 \leq t_i,k \leq 10^9,-10^9 \leq b_i \leq 10^9,0 \leq c_i \leq 1

来源

2024 华南师范大学百度杯新生赛 正式赛 Div.1 老生赛道

登录以提交代码。
单点时限 2 秒
内存限制 128 MB
提交 6
通过 2