힘겨운 쿠기의 식당 개업기

가톨릭대학교에서 고양이를 대상으로 식당을 운영하려고 하는 쿠기는 식당의 위치가 중요하다고 생각해서 최적의 위치를 고민하고 있다.

쿠기는 $N$마리 고양이들의 집의 좌표 $(X, Y)$와 출출함 $Z$를 조사했다. 고양이들의 집은 서로 같은 좌표에 존재하지 않는다.

쿠기가 사는 나라에는 임의의 좌표를 기준으로 좌표축에 고양이의 집이 있다면 그 좌표에 식당을 개업할 수 없다는 법이 있다. 식당의 좌표는 정수가 아니어도 된다.

식당을 원점으로 두고 사분면을 나눌 때, $S$와 $E$는 다음과 같다.

• $S_i$ = $i$ 사분면에 있는 고양이들의 출출함 $Z$의 합
• $E$ = ($S_1, S_2, S_3, S_4$) 중 최댓값 - ($S_1, S_2, S_3, S_4$) 중 최솟값
• $i$ 사분면에 고양이가 한 마리도 없으면 $S_i$는 0이다.
• 식당을 개업할 수 없는 좌표라면 $E$는 100,000,000이다.

쿠기는 $E$가 최솟값인 곳에 식당을 개업하려고 한다. 식당 개업 준비로 바쁜 쿠기를 도와 $E$의 최솟값을 구하여라.

첫째 줄에 정수 $N$ ($4 \le N \le 1,000$)이 주어진다.

둘째 줄부터 $N + 1$줄까지 각 고양이의 세 정수 $X$ ($-100,000,000 \le X \le 100,000,000$), $Y$ ($-100,000,000 \le Y \le 100,000,000$), $Z$ ($1 \le Z \le 1,000$)가 주어진다.

$E$의 최솟값을 출력한다.