分数: 500 点
问题陈述
我们有一个网格 10^9 行和 10^9 列。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
对于 i=1,2,\ldots,N,一个正整数 x_i 写在 (r_i,c_i)。另一方面 10^{18}-N 正方形, 写入 0 。
你选择一个正方形 (R,C) 并计算总和 S 上写的整数 2 \times 10^9 - 1 与以下对象共享行或列的方块 (R,C).
找出最大可能值 S.
约束
- 1 \leq N \leq 2 \times 10^5
- 1 \leq r_i,c_i,x_i \leq 10^9
- (r_i,c_i) \neq (r_j,c_j) if i \neq 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) as (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