시간 제한메모리 제한제출정답맞은 사람정답 비율
4 초 (추가 시간 없음) 1024 MB (추가 메모리 없음)1881008154.000%

문제

"츠바메가에시"(つばめがえし)는 일본의 검사 "사사키 코지로"가 날아가는 제비를 베었다고 전해지는 검 초식의 이름이다. 기록상으로는 세 번 연속 칼질을 했다고 전해지나, 실제로 기술을 재연해 본 바에 따르면 두 번 연속 까지가 한계라고 한다. 하지만 세 번 연속 베는 것이 더 멋있어 보이므로 게임이나 애니메이션 등의 미디어에서 이 기술을 묘사할 때는 검격을 세 번 하는 모습을 주로 볼 수 있다.

미디어에 영향을 많이 받은 pichulia는 세 번 연속 베는 기술을 재연하고자 한다. 피나는 노력 끝에 pichulia는 마침내 X 축 또는 Y 축과 평행한 무한한 길이의 직선 형태의 검격을 구사할 수 있게 되었다.

연습은 끝났고 이제는 실전이다. 하지만 pichulia는 야생생물 보호 및 관리에 관한 법률 제19조 1항에 의거해 야생의 제비를 벨 수 없었고, 부득이하게 제비뽑기의 제비를 베기로 결심했다.

2차원 평면상에 $N$개의 제비가 있고, 각 제비마다 베었을 때 얻을 수 있는 점수를 가지고 있다. 정확히 세 번의 검격을 통해 얻을 수 있는 점수의 최댓값을 구해보자.

점수는 검격들에 베인 제비의 점수들의 합이다. 단, 한 제비를 여러 번 베어도 점수는 한 번만 더해진다.

그림 D.1: 2차원 평면상에 배치된 제비 그림 D.2: 세 번의 검격으로 제비를 베는 모습

입력

첫 번째 줄에는 제비의 개수 $N$($ 1 \leq N \leq 300\ 000 $)이 주어진다.

두 번째 줄부터 $N+1$번째 줄까지 $N$줄에 걸쳐서 세 정수 $x$, $y$, $v$가 공백으로 구분되어 주어진다. 이는 2차원 평면상의 좌표 ($x$, $y$) 에 점수가 $v$ 인 제비가 있음을 의미한다. ($0 \leq x, y \leq 1\ 000\ 000$, $1 \leq v \leq 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