背景

仙台には仙台駅を中心に南北線・東西線という 2 本の地下鉄が通っています。 ( wikipedia / 仙台市地下鉄 )

問題文

2 次元平面上に N 個の都市があります。i 番目の都市は座標 (x_i, y_i) に位置し、人口が p_i 人です。

あなたは都市を一つ選び、選んだ都市を基点として（ x 軸に平行な）東西方向・（ y 軸に平行な）南北方向に無限に伸びる地下鉄を敷設しようと考えています。

都市を適切に選ぶことで、地下鉄を利用できる人数の最大値を求めてください。 ただし、地下鉄を利用できる人とは、地下鉄が通る都市に住むすべての人を指します。

制約

• 1 \leq N \leq 2 \times 10^5
• 1 \leq x_i, y_i \leq 2 \times 10^5
• 1 \leq p_i \leq 10^9
• (x_i, y_i) \neq (x_j, y_j) \, (i \neq j)
• 入力はすべて整数

入力例 1

4
10 7 40
12 12 50
5 7 10
5 10 30

出力例 1

80

3 番目の都市を選ぶと、直線 x = 5, y = 7 上に地下鉄が敷設されます。 このとき、都市 1 、都市 3 、都市 4 に住む 40 + 10 + 30 = 80 人が地下鉄を利用でき、これが最大値となります。

入力例 2

5
1 1 1
1 2 1
2 2 1
2 3 1
3 3 1

出力例 2

3

座標 (1, 3) を基点とする地下鉄は敷設できないことに注意してください。

入力例 3

15
3 5 636708929
2 8 994903426
9 9 607399553
8 8 827889418
9 5 668774629
3 9 811132635
10 7 890433514
5 6 742283973
1 1 912497044
4 9 946700459
1 4 730139009
1 9 843207307
7 4 728535529
2 4 950182766
9 1 523704155

出力例 3

4851076007

答えは 32 bit 整数型に収まらない場合があります。