棋盘分值

题目描述

存在一张极大的网格棋盘，行列范围均为 $1\sim 10^9$。

棋盘上仅有 $N$ 个特殊格子拥有分值，其余所有格子分值均为 $0$。 其中第 $i$ 个特殊格子位于 $(r_i,c_i)$，分值为 $x_i$，保证所有特殊格子位置互不重复。

你可以任选一个格子 $(R,C)$，定义得分总值 $S$ 为： 第 $R$ 行所有格子分值 + 第 $C$ 列所有格子分值（交点格子仅计算一次）。

请求出可以获得的最大得分 $S$。

输入格式

N
r1 c1 x1
r2 c2 x2
...
rN cN xN

输出格式

输出可取得的最大得分值。

输入输出样例 #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 \le N \le 2\times 10^5$
• $1 \le r_i,c_i,x_i \le 10^9$
• 所有特殊格子坐标互不相同
• 输入均为整数

样例解释 1

选择坐标 $(2,2)$ 时，行列总分取得最大值 $20$。