问题描述

我们有一个 $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$ 的最大可能值。

约束条件

• $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)$。
• 输入中的所有值都是整数。

输入

从标准输入中以以下格式给出：

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

输出

输出答案。

示例输入 1

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

示例输出 1

20

如果你选择 $(2,2)$ 作为 $(R,C)$，那么 $S$ 将是 $20$，这是最大可能的值。

示例输入 2

1
1 1000000000 1

示例输出 2

1

示例输入 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