在二维平面上有 $N$ 个怪物。每个怪物都有一个与之关联的价值。

一次挥剑斩击可以消灭沿某条直线上的所有怪物。如果你消灭了一个怪物，该怪物就会消失。这条直线必须平行于其中一个坐标轴。

计算在最多可以进行三次挥剑斩击的情况下，你能消灭的怪物的最大价值总和。

输入格式

第一行给出一个整数 $N$ ($1 \le N \le 300\,000$)。

接下来的 $N$ 行，每行包含三个整数 $x, y, v$，表示在 $(x, y)$ 处有一个价值为 $v$ 的怪物 ($0 \le x, y \le 1\,000\,000$，$1 \le v \le 7\,000$)。

所有怪物的位置互不相同。

输出格式

输出在最多可以进行三次挥剑斩击的情况下，你能消灭的怪物的最大价值总和。

样例

输入样例 1

10
1 1 8
1 4 1
1 5 9
2 3 2
2 4 1
3 1 9
3 2 9
3 4 4
4 3 3
5 4 7

输出样例 1

48

输入样例 2

8
1 0 1
1 1000000 1
2 1 1
2 999999 1
3 2 1
3 999998 1
4 3 1
4 999997 1

输出样例 2

6

输入样例 3

1
1 1 3

输出样例 3

3