捕捉 Snuke (2D)

题目描述

高桥君正在尝试捕捉许多 Snuke。

在二维坐标平面上有一些与 Snuke 的巢穴相连的坑。

现在，$N$ 只 Snuke 将从坑中出现。已知第 $i$ 只 Snuke 会在时间 $T_i$ 从坐标 $(X_i,Y_i)$ 的坑中出现，其大小为 $A_i$。

高桥君在时间 $0$ 位于坐标 $(0,0)$，可以进行以下两种移动。

• 以最大速度 $1$ 在 $x$ 方向（正方向或负方向）移动。
• 以最大速度 $1$ 在 $y$ 正方向移动。

不允许向 $y$ 负方向移动。

当且仅当 Snuke 出现时他恰好位于该坑的坐标处，才能捕捉到这只 Snuke。

捕捉 Snuke 所需的时间可以忽略不计。

求高桥君通过最优移动能够捕捉到的 Snuke 大小之和的最大值。

输入格式

输入按以下格式从标准输入给出：

$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$

输出格式

以整数形式输出答案。

样例

3
1 0 0 100
3 2 1 10
5 3 1 1

101

最优策略如下。

在坐标 $(0,0)$ 等待，在时间 $1$ 捕捉第一只 Snuke。

前往坐标 $(3,1)$，在时间 $5$ 捕捉第三只 Snuke。

无法同时捕捉第一只和第二只 Snuke，因此这是最优方案。

2
100 0 1 1
200 1 0 10

10

不允许向 $y$ 负方向移动，因此无法先捕捉第一只 Snuke 再捕捉第二只。

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

1553741733

数据范围

• $1 \le N \le 10^5$
• $1 \le T_i \le 10^9$
• $0 \le X_i,Y_i \le 10^9$
• $1 \le A_i \le 10^9$
• 三元组 $(T_i,X_i,Y_i)$ 互不相同
• 输入中的所有值均为整数