题目描述

高桥想要捕捉很多个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大小之和的最大值。

约束条件

• $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)$等待，在时间$1$时捕捉第一只Snuke。
• 前往坐标$(3,1)$，在时间$5$时捕捉第三只Snuke。

无法同时捕捉到第一只和第二只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