102667: [AtCoder]ABC266 Ex - Snuke Panic (2D)

Problem Statement

Takahashi is trying to catch many Snuke.

There are some pits in a two-dimensional coordinate plane, connected to Snuke's nest.

Now, $N$ Snuke will appear from the pits. It is known that the $i$-th Snuke will appear from the pit at coordinates $(X_i,Y_i)$ at time $T_i$, and its size is $A_i$.

Takahashi is at coordinates $(0,0)$ at time $0$ and can do the following two kinds of moves.

• Move at a speed of at most $1$ in the $x$-direction (positive or negative).
• Move at a speed of at most $1$ in the positive $y$-direction.

Moving in the negative $y$-direction is not allowed.

He can catch a Snuke appearing from a pit if and only if he is at the coordinates of that pit exactly when it appears.
The time it takes to catch a Snuke is negligible.

Find the maximum sum of the sizes of Snuke that Takahashi can catch by moving optimally.

Constraints

• $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$
• The triples $(T_i,X_i,Y_i)$ are distinct.
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

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

Output

Print the answer as an integer.

Sample Input 1

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

Sample Output 1

101

The optimal strategy is as follows.

• Wait at coordinates $(0,0)$ to catch the first Snuke at time $1$.
• Go to coordinates $(3,1)$ to catch the third Snuke at time $5$.

It is impossible to catch both the first and second Snuke, so this is the best he can.

Sample Input 2

2
100 0 1 1
200 1 0 10

Sample Output 2

10

Moving in the negative $y$-direction is not allowed, so he cannot catch the first Snuke and then the second.

Sample Input 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

Sample Output 3

1553741733

问题描述

Takahashi 正在试图捕捉许多 Snuke。

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

现在，有 $N$ 只 Snuke 会从坑里出现。已知第 $i$ 只 Snuke 会在时间 $T_i$ 从坐标 $(X_i,Y_i)$ 的坑里出现，它的大小是 $A_i$。

Takahashi 在时间 $0$ 位于坐标 $(0,0)$，可以进行以下两种移动方式：

• 以最多 $1$ 的速度向 $x$ 轴（正或负）方向移动。
• 以最多 $1$ 的速度向 正 $y$ 轴方向移动。

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

如果他在 Snuke 出现的那一刻恰好在那个坑的坐标上，那么他就能捕捉到那只 Snuke。捕捉 Snuke 所需的时间可以忽略不计。

通过最佳移动，找到 Takahashi 可以捕捉到的最大 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