在 \text{kkz} 好好读书的时候，\text{crq} 溜出去看烟花了！
\text{crq} 在一条烟花街道上，烟花街道有 n 个烟花燃放点，分别按 1 \sim n 标号，标号相邻燃放点之间距离 1 单位距离。
将会有 m 束烟花在街道上燃放，同时同地只会燃放至多一束烟花。
已知每个烟花的燃放点 a_i、烟花的精彩值 b_i、烟花的颜色 c_i、燃放时间 t_i。
如果 t_i 时，\text{crq} 位于燃放点 a_i，则可以选择观看第 i 束烟花。
最初 \text{crq} 的快乐值为 0，在观看第 i 束烟花后 \text{crq} 的快乐值会发生下面的变化：
\text{crq} 的快乐值增加 b_i。
若 c_i=1，\text{crq} 的快乐值变为原来的相反数。
假设初始时间 t=0，初始时 \text{crq} 的位置任选，每 1 单位时间 \text{crq} 可以移动至多 k 单位距离，求在所有烟花燃放结束后，\text{crq} 快乐值的最大值。
输入
第一行包含三个整数 n,m,k，分别表示烟花燃放点总数、烟花总数和 \text{crq} 的移动速度。
接下来 m 行每行包含 4 个整数，分别表示 a_i,b_i,c_i,t_i。
输出
输出一行一个整数，表示在所有烟花燃放结束后，\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】
| t | 位置 | 快乐值 |
|---|---|---|
| 1 | 1 | 0 |
| 2 | 1 | 1 |
| 3 | 4 | -11 |
| 4 | 1 | 20 |
| 5 | 1 | 28 |
【数据范围】
对于所有的测试数据，保证 1 \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 老生赛道