当前没有测试数据。

Ex - Snuke Panic (2D)

得分：600分

问题描述

小高正在试图捕捉许多Snuke。

二维坐标平面上有一些陷阱，连接到Snuke的巢穴。

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

小高在时间$0$位于坐标$(0,0)$处，并且可以进行以下两种移动：

• 在$x$-方向以速度至多$1$移动。
• 在正$y$-方向以速度至多$1$移动。

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

只有当他在Snuke出现的坐标处时，才能捕捉到从陷阱中出现的Snuke。
捕捉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$

输出

以整数形式输出答案。

---

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