Codeforces Round 1133 (Div. 1, Div. 2) is coming soon! Register here. ×
D. Triple Sword Strike
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

There are $$$N$$$ monsters on a two-dimensional plane. Each monster has a value associated with it.

A sword strike is an action that slays all monsters along a line. If you slay a monster, the monster disappears. The line must be parallel to one of the coordinate axes.

Compute the maximum sum of values of monsters that you can slay given that you can perform up to three sword strikes.

Input

In the first line, a single integer $$$N$$$ is given ($$$ 1 \leq N \leq 300\,000 $$$). Each of the next $$$N$$$ lines contains three integers $$$x, y, v$$$, indicating there is a monster located at $$$(x, y)$$$ with value $$$v$$$ ($$$0 \leq x, y \leq 1\,000\,000$$$, $$$1 \leq v \leq 7\,000$$$).

All monsters are at distinct locations.

Output

Output the maximum sum of values of monsters that you can slay given that you can perform up to three sword strikes.

Examples
Input
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
Output
48
Input
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
Output
6
Input
1
1 1 3
Output
3