409921: GYM103855 D Triple Sword Strike

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.

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 the maximum sum of values of monsters that you can slay given that you can perform up to three sword strikes.

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

48

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

6

1
1 1 3

3