시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 200 54 45 34.884%

문제

세 마을의 좌표가 (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)

출력

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

예제 입력 1

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

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6Ijk3NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWI5YzhcdWM3NDRcdWM3NTggXHVjZTVjXHViYzAwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxMzggXHViOWM4XHVjNzQ0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCB6PHN1Yj4xPFwvc3ViPiksICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4sIHo8c3ViPjI8XC9zdWI+KSwgKHg8c3ViPjM8XC9zdWI+LCB5PHN1Yj4zPFwvc3ViPiwgejxzdWI+MzxcL3N1Yj4pXHVjNzc0XHViNzdjXHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNzc0XHViNTRjLCBcdWMxMzggXHViOWM4XHVjNzQ0XHVjNzQ0IFx1Y2U1Y1x1YmMwMFx1YjNjNFx1YjI5NCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IFx1YWQ2Y1x1ZDU2MCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWNlNWNcdWJjMDBcdWIzYzQgPSBkPHN1Yj4xMjxcL3N1Yj4gKyBkPHN1Yj4yMzxcL3N1Yj4gKGQ8c3ViPmlqPFwvc3ViPiA9IHx4PHN1Yj5pPFwvc3ViPiAtIHg8c3ViPmo8XC9zdWI+fCArIHx5PHN1Yj5pPFwvc3ViPiAtIHk8c3ViPmo8XC9zdWI+fCArIHx6PHN1Yj5pPFwvc3ViPiAtIHo8c3ViPmo8XC9zdWI+fCk8XC9wPlxyXG5cclxuPHA+XHViOWM4XHVjNzQ0XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjMTM4IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWNlNWNcdWJjMDBcdWIzYzRcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWMyMTggTiAoMyAmbGU7IE4gJmxlOyAxMCwwMDApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjljOFx1Yzc0NFx1Yzc1OCBcdWM3MDRcdWNlNTggKHgsIHksIHopXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xMDAwICZsZTsgeCx5LHogJmxlOyAxMDAwKTxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YzEzOCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjZTVjXHViYzAwXHViM2M0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiOTc2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IjMgbmVhcmVzdCB2aWxsYWdlcyIsImRlc2NyaXB0aW9uIjoiPHA+QXNzdW1lIHRoZSBsb2NhdGlvbnMgb2YgYW55IHRocmVlIHZpbGxhZ2VzIGFyZSAoeDxzdWI+MTxcL3N1Yj4sIHk8c3ViPjE8XC9zdWI+LCB6PHN1Yj4xPFwvc3ViPiksICh4PHN1Yj4yPFwvc3ViPiwgeTxzdWI+MjxcL3N1Yj4sIHo8c3ViPjI8XC9zdWI+KSwgYW5kICh4PHN1Yj4zPFwvc3ViPiwgeTxzdWI+MzxcL3N1Yj4sIHo8c3ViPjM8XC9zdWI+KS4gVGhlIGRpc3RhbmNlIG9mIHRoZSBwYXRocyBwYXNzaW5nIHRocm91Z2ggYW55IHRocmVlIHZpbGxhZ2VzIGFyZSBkZWZpbmVkIGFzJm5ic3A7PFwvcD5cclxuXHJcbjxwPkQgPSZuYnNwO2Q8c3ViPjEyPFwvc3ViPiZuYnNwOysgZDxzdWI+MjM8XC9zdWI+LCB3aGVyZSBkPHN1Yj5pajxcL3N1Yj4mbmJzcDs9IHx4PHN1Yj5pPFwvc3ViPiZuYnNwOy0geDxzdWI+ajxcL3N1Yj58ICsgfHk8c3ViPmk8XC9zdWI+Jm5ic3A7LSB5PHN1Yj5qPFwvc3ViPnwgKyB8ejxzdWI+aTxcL3N1Yj4mbmJzcDstIHo8c3ViPmo8XC9zdWI+fDxcL3A+XHJcblxyXG48cD5EZXRlcm1pbmUgdGhlIHNob3J0ZXN0IHBhdGggcGFzc2luZyB0aHJvdWdoIHRoZSB0aHJlZSBjbG9zZXN0IHZpbGxhZ2VzLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgc3BlY2lmaWVzIHRoZSBudW1iZXIgb2YgdmlsbGFnZXMsIE4gKHdoZXJlIDMgJmx0Oz0gTiAmbHQ7PSAxMCwwMDApLiBFYWNoIG9mIHRoZSBmb2xsb3dpbmcgTiBsaW5lcyBzcGVjaWZpZXMgdGhlIGxvY2F0aW9uICh4LCB5LCB6KSBvZiBlYWNoIHZpbGxhZ2UgKHdoZXJlIC0xMDAwICZsdDs9IHgsIHksIHogJmx0Oz0gMTAwMCkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T25lIGxpbmUgc3BlY2lmaWVzIHRoZSBsZW5ndGggb2YgdGhlIHNob3J0ZXN0IHBhdGggcGFzc2luZyB0aHJvdWdoIHRoZSB0aHJlZSBjbG9zZXN0IHZpbGxhZ2VzLiZuYnNwOzxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=