题目描述

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

输出格式

答えを出力せよ。

题目大意

在 $10^9\times10^9$ 平面上有 $n$ 个点有大于零的值，其余的点均为 $0$。现在你选择一个点，使得所在列的所有值的和，加上所在的行的所有值的和，减去当前点的值最大。求这个最大值。

translated by 月。

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

20

1
1 1000000000 1

1

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

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)$
• 入力はすべて整数

Sample Explanation 1

$(R,C)$ として $(2,2)$ を選ぶと $S$ が $20$ となります。これが最大値です。