시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 115 36 32 39.024%

문제

세 마을의 좌표가 (x1, y1, z1), (x2, y2, z2), (x3, y3, z3)이라고 가정해보자. 이 때, 세 마을을 친밀도는 아래와 같이 구할 수 있다.

친밀도 = d12 + d23 (dij = |xi - xj| + |yi - yj| + |zi - zj|)

마을이 주어졌을 때, 가장 작은 세 마을의 친밀도를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 마을의 수 N (3 ≤ N ≤ 10,000)이 주어진다. 다음 N개 줄에는 마을의 위치 (x, y, z)가 주어진다. (-1000 ≤ x,y,z ≤ 1000)

출력

세 마을의 친밀도 중 가장 작은 값을 출력한다.

예제 입력

9
0 0 1
0 0 2
0 0 3
0 0 4
0 0 6
0 0 8
0 0 7
0 0 9
0 0 10

예제 출력

2

힌트