AT_abc266_h [ABC266Ex] Snuke Panic (2D)

题目描述

高桥君正在试图抓住すぬけ君们。

在二维坐标平面上有若干个洞，通向すぬけ君们的巢穴。

接下来有 $N$ 只すぬけ君会从这些洞里出来。第 $i$ 只すぬけ君会在时刻 $T_i$ 从坐标 $(X_i, Y_i)$ 的洞里出来，且其大小为 $A_i$。

高桥君一开始在时刻 $0$，坐标 $(0,0)$，他可以进行以下两种移动：

• 以每单位时间不超过 $1$ 的速度在 $x$ 轴方向移动；
• 以每单位时间不超过 $1$ 的速度在 $y$ 轴正方向移动。

他不能向 $y$ 轴负方向移动。

只有当高桥君在すぬけ君出现的同一时刻、同一坐标时，才能抓住这只すぬけ君，并且只有在这种情况下才能抓住。抓住すぬけ君所需的时间可以忽略不计。

请你求出高桥君合理行动时，能够抓住的すぬけ君大小之和的最大值。

输入格式

输入按以下格式从标准输入读入。

$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

输入 #1

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

输出 #1

101

输入输出样例 #2

输入 #2

2
100 0 1 1
200 1 0 10

输出 #2

10

输入输出样例 #3

输入 #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

说明/提示

限制条件

• $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)$ 互不相同
• 输入中的所有数值均为整数

样例解释 1

• 在坐标 $(0,0)$ 等待，时刻 $1$ 抓住第 $1$ 只すぬけ君
• 移动到坐标 $(3,1)$，时刻 $5$ 抓住第 $3$ 只すぬけ君

无法同时抓住第 $1$ 只和第 $2$ 只すぬけ君，因此这就是最大值。

样例解释 2

由于不能向 $y$ 轴负方向移动，所以在抓住第 $1$ 只すぬけ君后，无法再抓住第 $2$ 只すぬけ君。

由 ChatGPT 4.1 翻译