分数: 600 点
问题陈述
高桥正试图抓住许多 Snuke。
二维坐标平面上有一些坑,与Snuke的巢穴相连。
现在, N 蛇将会从坑中出现。据了解, i-th Snuke 将从坐标处的坑中出现 (X_i,Y_i) 时间 T_i,其大小为 A_i.
高桥在坐标处 (0,0) 时间 0 并且可以做以下两种动作。
- 移动速度最多为 1 在 x- 方向(正或负)。
- 移动速度最多为 1 在 积极 y- 方向。
向负面移动 y- 不允许方向。
当且仅当他在蛇出现时正好位于该坑的坐标处时,他才能抓住从坑中出现的蛇。
捕捉 Snuke 所需的时间可以忽略不计。
求高桥通过最佳移动可以捕获的 Snuke 大小的最大总和。
约束
- 1 \leq N \leq 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq X_i,Y_i \leq 10^9
- 1 \leq A_i \leq 10^9
- 三元组 (T_i,X_i,Y_i) 是不同的。
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N T_1 X_1 Y_1 A_1 T_2 X_2 Y_2 A_2 \vdots T_N X_N Y_N A_N
输出
将答案打印为整数。
示例输入 1
3 1 0 0 100 3 2 1 10 5 3 1 1
示例输出 1
101
最优策略如下。
- 在坐标处等待 (0,0) 及时抓住第一个 Snuke 1.
- 转到坐标 (3,1) 及时抓住第三个 Snuke 5.
不可能同时抓住第一个和第二个 Snuke,所以这是他能做的最好的了。
示例输入 2
2 100 0 1 1 200 1 0 10
示例输出 2
10
向负面移动 y- 方向是不允许的,所以他不能抓住第一个 Snuke,然后抓住第二个。
示例输入 3
10 797829355 595605750 185676190 353195922 913575467 388876063 395940406 533206504 810900084 201398242 159760440 87027328 889089200 220046203 85488350 325976483 277429832 161055688 73308100 940778720 927999455 429014248 477195779 174616807 673419335 415891345 81019893 286986530 989248231 147792453 417536200 219371588 909664305 22150727 414107912 317441890 988670052 140275628 468278658 67181740
示例输出 3
1553741733