츠바메가에시

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

매체의 영향을 많이 받은 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$)

모든 제비의 위치는 서로 다르다.

정확히 세 번의 검격을 통해 얻을 수 있는 점수의 최댓값을 출력한다.