在 好好读书的时候, 溜出去看烟花了!
在一条烟花街道上,烟花街道有 个烟花燃放点,分别按 标号,标号相邻燃放点之间距离 单位距离。
将会有 束烟花在街道上燃放,同时同地只会燃放至多一束烟花。
已知每个烟花的燃放点 、烟花的精彩值 、烟花的颜色 、燃放时间 。
如果 时, 位于燃放点 ,则可以选择观看第 束烟花。
最初 的快乐值为 ,在观看第 束烟花后 的快乐值会发生下面的变化:
的快乐值增加 。
若 , 的快乐值变为原来的相反数。
假设初始时间 ,初始时 的位置任选,每 单位时间 可以移动至多 单位距离,求在所有烟花燃放结束后, 快乐值的最大值。
输入
第一行包含三个整数 ,分别表示烟花燃放点总数、烟花总数和 的移动速度。
接下来 行每行包含 个整数,分别表示 。
输出
输出一行一个整数,表示在所有烟花燃放结束后, 快乐值的最大值。
样例
标准输入 复制文本 |
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】
【数据范围】
对于所有的测试数据,保证 。
来源
2024 华南师范大学百度杯新生赛 正式赛 Div.1 老生赛道