AT_abc298_f [ABC298F] Rook Score

题目描述

有一个纵向 $10^9$ 格、横向 $10^9$ 格的网格。第 $i$ 行第 $j$ 列的格子记作 $(i, j)$。

对于 $i=1,2,\ldots,N$，在 $(r_i, c_i)$ 这个格子上写有正整数 $x_i$，其余 $10^{18}-N$ 个格子上写有 $0$。

你可以选择一个格子 $(R, C)$，然后计算与 $(R, C)$ 同一行或同一列的 $2 \times 10^9 - 1$ 个格子上所写整数的总和 $S$。

请你求出 $S$ 可能取得的最大值。

输入格式

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

$N$
$r_1$ $c_1$ $x_1$
$\vdots$
$r_N$ $c_N$ $x_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

4
1 1 2
1 2 9
2 1 8
3 2 3

输出 #1

20

输入输出样例 #2

输入 #2

1
1 1000000000 1

输出 #2

1

输入输出样例 #3

输入 #3

15
158260522 877914575 602436426
24979445 861648772 623690081
433933447 476190629 262703497
211047202 971407775 628894325
731963982 822804784 450968417
430302156 982631932 161735902
880895728 923078537 707723857
189330739 910286918 802329211
404539679 303238506 317063340
492686568 773361868 125660016
650287940 839296263 462224593
492601449 384836991 191890310
576823355 782177068 404011431
818008580 954291757 160449218
155374934 840594328 164163676

输出 #3

1510053068

说明/提示

限制条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq r_i, c_i, x_i \leq 10^9$
• 若 $i \neq j$，则 $(r_i, c_i) \neq (r_j, c_j)$
• 输入均为整数

样例解释 1

如果选择 $(R, C) = (2, 2)$，则 $S = 20$，这是最大值。

由 ChatGPT 4.1 翻译