{"raw_statement":[{"iden":"problem statement","content":"We have a grid with $10^9$ rows and $10^9$ columns. Let $(i,j)$ denote the square at the $i$\\-th row from the top and $j$\\-th column from the left.\nFor $i=1,2,\\ldots,N$, a positive integer $x_i$ is written on $(r_i,c_i)$. On the other $10^{18}-N$ squares, $0$ is written.\nYou choose a square $(R,C)$ and compute the sum $S$ of the integers written on the $2 \\times 10^9 - 1$ squares that share a row or column with $(R,C)$.\nFind the maximum possible value of $S$."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $1 \\leq r_i,c_i,x_i \\leq 10^9$\n*   $(r_i,c_i) \\neq (r_j,c_j)$ if $i \\neq j$.\n*   All values in the input are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$r_1$ $c_1$ $x_1$\n$\\vdots$\n$r_N$ $c_N$ $x_N$"},{"iden":"sample input 1","content":"4\n1 1 2\n1 2 9\n2 1 8\n3 2 3"},{"iden":"sample output 1","content":"20\n\nIf you choose $(2,2)$ as $(R,C)$, then $S$ will be $20$, which is the maximum possible value."},{"iden":"sample input 2","content":"1\n1 1000000000 1"},{"iden":"sample output 2","content":"1"},{"iden":"sample input 3","content":"15\n158260522 877914575 602436426\n24979445 861648772 623690081\n433933447 476190629 262703497\n211047202 971407775 628894325\n731963982 822804784 450968417\n430302156 982631932 161735902\n880895728 923078537 707723857\n189330739 910286918 802329211\n404539679 303238506 317063340\n492686568 773361868 125660016\n650287940 839296263 462224593\n492601449 384836991 191890310\n576823355 782177068 404011431\n818008580 954291757 160449218\n155374934 840594328 164163676"},{"iden":"sample output 3","content":"1510053068"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}