시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 170 45 38 35.849%

문제

세 마을의 좌표가 (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+MzxcL3N1Yj4pXHVjNzc0XHViNzdjXHVhY2UwIFx1YWMwMFx1YzgxNVx1ZDU3NFx1YmNmNFx1Yzc5MC4gXHVjNzc0IFx1YjU0YywgXHVjMTM4IFx1YjljOFx1Yzc0NFx1Yzc0NCBcdWNlNWNcdWJjMDBcdWIzYzRcdWIyOTQgXHVjNTQ0XHViNzk4XHVjNjQwIFx1YWMxOVx1Yzc3NCBcdWFkNmNcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjZTVjXHViYzAwXHViM2M0ID0gZDxzdWI+MTI8XC9zdWI+ICsgZDxzdWI+MjM8XC9zdWI+IChkPHN1Yj5pajxcL3N1Yj4gPSB8eDxzdWI+aTxcL3N1Yj4gLSB4PHN1Yj5qPFwvc3ViPnwgKyB8eTxzdWI+aTxcL3N1Yj4gLSB5PHN1Yj5qPFwvc3ViPnwgKyB8ejxzdWI+aTxcL3N1Yj4gLSB6PHN1Yj5qPFwvc3ViPnwpPFwvcD5cclxuXHJcbjxwPlx1YjljOFx1Yzc0NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzEzOCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjZTVjXHViYzAwXHViM2M0XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjMjE4IE4gKDMgJmxlOyBOICZsZTsgMTAsMDAwKVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWI5YzhcdWM3NDRcdWM3NTggXHVjNzA0XHVjZTU4ICh4LCB5LCB6KVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgtMTAwMCAmbGU7IHgseSx6ICZsZTsgMTAwMCk8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWMxMzggXHViOWM4XHVjNzQ0XHVjNzU4IFx1Y2U1Y1x1YmMwMFx1YjNjNCBcdWM5MTEgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijk3NjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiIzIG5lYXJlc3QgdmlsbGFnZXMiLCJkZXNjcmlwdGlvbiI6IjxwPkFzc3VtZSB0aGUgbG9jYXRpb25zIG9mIGFueSB0aHJlZSB2aWxsYWdlcyBhcmUgKHg8c3ViPjE8XC9zdWI+LCB5PHN1Yj4xPFwvc3ViPiwgejxzdWI+MTxcL3N1Yj4pLCAoeDxzdWI+MjxcL3N1Yj4sIHk8c3ViPjI8XC9zdWI+LCB6PHN1Yj4yPFwvc3ViPiksIGFuZCAoeDxzdWI+MzxcL3N1Yj4sIHk8c3ViPjM8XC9zdWI+LCB6PHN1Yj4zPFwvc3ViPikuIFRoZSBkaXN0YW5jZSBvZiB0aGUgcGF0aHMgcGFzc2luZyB0aHJvdWdoIGFueSB0aHJlZSB2aWxsYWdlcyBhcmUgZGVmaW5lZCBhcyZuYnNwOzxcL3A+XHJcblxyXG48cD5EID0mbmJzcDtkPHN1Yj4xMjxcL3N1Yj4mbmJzcDsrIGQ8c3ViPjIzPFwvc3ViPiwgd2hlcmUgZDxzdWI+aWo8XC9zdWI+Jm5ic3A7PSB8eDxzdWI+aTxcL3N1Yj4mbmJzcDstIHg8c3ViPmo8XC9zdWI+fCArIHx5PHN1Yj5pPFwvc3ViPiZuYnNwOy0geTxzdWI+ajxcL3N1Yj58ICsgfHo8c3ViPmk8XC9zdWI+Jm5ic3A7LSB6PHN1Yj5qPFwvc3ViPnw8XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIHRoZSBzaG9ydGVzdCBwYXRoIHBhc3NpbmcgdGhyb3VnaCB0aGUgdGhyZWUgY2xvc2VzdCB2aWxsYWdlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIHNwZWNpZmllcyB0aGUgbnVtYmVyIG9mIHZpbGxhZ2VzLCBOICh3aGVyZSAzICZsdDs9IE4gJmx0Oz0gMTAsMDAwKS4gRWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgc3BlY2lmaWVzIHRoZSBsb2NhdGlvbiAoeCwgeSwgeikgb2YgZWFjaCB2aWxsYWdlICh3aGVyZSAtMTAwMCAmbHQ7PSB4LCB5LCB6ICZsdDs9IDEwMDApLiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk9uZSBsaW5lIHNwZWNpZmllcyB0aGUgbGVuZ3RoIG9mIHRoZSBzaG9ydGVzdCBwYXRoIHBhc3NpbmcgdGhyb3VnaCB0aGUgdGhyZWUgY2xvc2VzdCB2aWxsYWdlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d