시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1928 715 492 37.615%

문제

때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만드려고 한다.

행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다.

민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 하려고 한다. 이 때, 모든 행성을 터널로 연결하는데 필요한 최소 비용을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이상 있는 경우는 없다. 

출력

첫째 줄에 모든 행성을 터널로 연결하는데 필요한 최소 비용을 출력한다.

예제 입력 1

5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19

예제 출력 1

4
W3sicHJvYmxlbV9pZCI6IjI4ODciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQ1ODlcdWMxMzEgXHVkMTMwXHViMTEwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWI1NGNcdWIyOTQgMjA0MFx1YjE0NCwgXHVjNzc0XHViYmZjXHVkNjAxXHVjNzQwIFx1YzZiMFx1YzhmY1x1YzVkMCBcdWM3OTBcdWMyZTBcdWI5Y2NcdWM3NTggXHVjNjU1XHVhZDZkXHVjNzQ0IFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC4gXHVjNjU1XHVhZDZkXHVjNzQwIE5cdWFjMWNcdWM3NTggXHVkNTg5XHVjMTMxXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YmJmY1x1ZDYwMVx1Yzc3NFx1YjI5NCBcdWM3NzQgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1ZDZhOFx1YzcyOFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM5YzBcdWJjMzBcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQ0IFx1YjljY1x1YjRkY1x1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1ZDU4OVx1YzEzMVx1Yzc0MCAzXHVjYzI4XHVjNmQwIFx1Yzg4Y1x1ZDQ1Y1x1YzcwNFx1Yzc1OCBcdWQ1NWMgXHVjODEwXHVjNzNjXHViODVjIFx1YzBkZFx1YWMwMVx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuIFx1YjQ1MCBcdWQ1ODlcdWMxMzEgQSh4PHN1Yj5BPFwvc3ViPiwgeTxzdWI+QTxcL3N1Yj4sIHo8c3ViPkE8XC9zdWI+KVx1YzY0MCBCKHg8c3ViPkI8XC9zdWI+LCB5PHN1Yj5CPFwvc3ViPiwgejxzdWI+QjxcL3N1Yj4pXHViOTdjIFx1ZDEzMFx1YjExMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NjAgXHViNTRjIFx1YjRkY1x1YjI5NCBcdWJlNDRcdWM2YTlcdWM3NDAgbWluKHx4PHN1Yj5BPFwvc3ViPi14PHN1Yj5CPFwvc3ViPnwsIHx5PHN1Yj5BPFwvc3ViPi15PHN1Yj5CPFwvc3ViPnwsIHx6PHN1Yj5BPFwvc3ViPi16PHN1Yj5CPFwvc3ViPnwpXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWJiZmNcdWQ2MDFcdWM3NzRcdWIyOTQgXHVkMTMwXHViMTEwXHVjNzQ0IFx1Y2QxZCBOLTFcdWFjMWMgXHVhYzc0XHVjMTI0XHVkNTc0XHVjMTFjIFx1YmFhOFx1YjRlMCBcdWQ1ODlcdWMxMzFcdWM3NzQgXHVjMTFjXHViODVjIFx1YzVmMFx1YWNiMFx1YjQxOFx1YWM4YyBcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWM3NzQgXHViNTRjLCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVjMTMxXHVjNzQ0IFx1ZDEzMFx1YjExMFx1Yjg1YyBcdWM1ZjBcdWFjYjBcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Y2Q1Y1x1YzE4YyBcdWJlNDRcdWM2YTlcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDU4OVx1YzEzMVx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgTiAmbGU7IDEwMCwwMDApIFx1YjJlNFx1Yzc0YyBOXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFjMDEgXHVkNTg5XHVjMTMxXHVjNzU4IHgsIHksIHpcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM4OGNcdWQ0NWNcdWIyOTQgLTEwPHN1cD45PFwvc3VwPlx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMDxzdXA+OTxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuIFx1ZDU1YyBcdWM3MDRcdWNlNThcdWM1ZDAgXHVkNTg5XHVjMTMxXHVjNzc0IFx1YjQ1MCBcdWFjMWMgXHVjNzc0XHVjMGMxIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViYWE4XHViNGUwIFx1ZDU4OVx1YzEzMVx1Yzc0NCBcdWQxMzBcdWIxMTBcdWI4NWMgXHVjNWYwXHVhY2IwXHVkNTU4XHViMjk0XHViMzcwIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWNkNWNcdWMxOGMgXHViZTQ0XHVjNmE5XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyODg3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiU1ZFTUlSIiwiZGVzY3JpcHRpb24iOiI8cD5Gb3VydGggR3JlYXQgYW5kIEJvdW50aWZ1bCBIdW1hbiBFbXBpcmUgaXMgZGV2ZWxvcGluZyBhIHRyYW5zY29uZHVpdCB0dW5uZWwgbmV0d29yayBjb25uZWN0aW5nIGFsbCBpdCYjMzk7cyBwbGFuZXRzLiBUaGUgRW1waXJlIGNvbnNpc3RzIG9mIE4gcGxhbmV0cywgcmVwcmVzZW50ZWQgYXMgcG9pbnRzIGluIHRoZSAzRCBzcGFjZS4gVGhlIGNvc3Qgb2YgZm9ybWluZyBhIHRyYW5zY29uZHVpdCB0dW5uZWwgYmV0d2VlbiBwbGFuZXRzIEEgYW5kIEIgaXM6PFwvcD5cclxuXHJcbjxwPlR1bm5lbENvc3RbQSxCXSA9IG1pbnsgfHhBLXhCfCwgfHlBLXlCfCwgfHpBLXpCfCB9PFwvcD5cclxuXHJcbjxwPndoZXJlICh4QSwgeUEsIHpBKSBhcmUgM0QgY29vcmRpbmF0ZXMgb2YgcGxhbmV0IEEsIGFuZCAoeEIsIHlCLCB6QikgYXJlIGNvb3JkaW5hdGVzIG9mIHBsYW5ldCBCLiBUaGUgRW1waXJlIG5lZWRzIHRvIGJ1aWxkIGV4YWN0bHkgTiAtIDEgdHVubmVscyBpbiBvcmRlciB0byBmdWxseSBjb25uZWN0IGFsbCBwbGFuZXRzLCBlaXRoZXIgYnkgZGlyZWN0IGxpbmtzIG9yIGJ5IGNoYWluIG9mIGxpbmtzLiBZb3UgbmVlZCB0byBjb21lIHVwIHdpdGggdGhlIGxvd2VzdCBwb3NzaWJsZSBjb3N0IG9mIHN1Y2Nlc3NmdWxseSBjb21wbGV0aW5nIHRoaXMgcHJvamVjdC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIG9uZSBpbnRlZ2VyIE4gKDEgJmxlOyBOICZsZTsgMTAwIDAwMCksIG51bWJlciBvZiBwbGFuZXRzLjxcL3A+XHJcblxyXG48cD5OZXh0IE4gbGluZXMgY29udGFpbiBleGFjdGx5IDMgaW50ZWdlcnMgZWFjaC4gQWxsIGludGVnZXJzIGFyZSBiZXR3ZWVuIC0xMDxzdXA+OTxcL3N1cD4gYW5kIDEwPHN1cD45PFwvc3VwPiBpbmNsdXNpdmUuIEVhY2ggbGluZSBjb250YWlucyB0aGUgeCwgeSwgYW5kIHogY29vcmRpbmF0ZSBvZiBvbmUgcGxhbmV0IChpbiBvcmRlcikuPFwvcD5cclxuXHJcbjxwPk5vIHR3byBwbGFuZXRzIHdpbGwgb2NjdXB5IHRoZSBleGFjdCBzYW1lIHBvaW50IGluIHNwYWNlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0aGUgbWluaW1hbCBjb3N0IG9mIGZvcm1pbmcgdGhlIG5ldHdvcmsgb2YgdHVubmVscy48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=