시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB48201845.000%

문제

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

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

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

식당을 기준으로 사분면이 있을 때, S E는 다음과 같다.

  • Si = i 사분면에 있는 고양이들의 출출함 Z의 합
  • E = (S1, S2, S3, S4) 중 최댓값 - (S1, S2, S3, S4) 중 최솟값
  • i 사분면에 고양이가 한 마리도 없을 때 Si는 0이다.
  • 식당을 개업할 수 없는 좌표라면, E는 100,000,000이다.

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

입력

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

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

출력

E의 최솟값을 출력한다.

예제 입력 1

6
-1 3 5
-1 -2 4
1 1 2
6 -4 6
-7 -7 1
5 7 4

예제 출력 1

1