문제 설명
루루 왕국은 N개의 섬으로 이루어진 섬나라이다. 루루 왕국의 국왕 루루는 국민들의 편의를 위해 N개의 섬을 모두 연결하는 다리 공사 프로젝트를 진행하려고 한다. 루루 왕국의 모든 섬은 좌표 (x, y)로 표현할 수 있으며, 섬과 섬 사이의 다리를 연결하는 비용은 x좌표와 y좌표 사이의 차이의 합만큼 소요된다. 예를 들어, (1, 2)위치의 섬과 (4, -1)위치의 섬을 연결하는 다리를 건설하기 위해서는 x좌표의 차이와 y좌표의 차이의 합인 6만큼의 비용이 필요하다. 다리는 항상 연결된 양 끝의 섬으로만 이동할 수 있으며, 중간에 다른 다리나 섬으로 이동할 수 없다.
루루 왕국에 스파이로 잠입한 여러분은 국왕 루루의 신임을 얻어 다리 공사 프로젝트의 총괄을 맡게 되었다. 여러분의 목표는 루루 왕국의 국비를 낭비하는 것으로, 다른 사람들이 당신의 정체를 눈치 채지 못 하게 건설하는 다리의 개수는 최소로 하되, 사용되는 국비를 최대로 만들고자 한다. N개의 섬의 좌표가 주어질 때, 여러분이 프로젝트를 진행하는데 필요한 비용을 구하시오. 단, 여러 개의 다리를 거쳐서 이동할 수 있으면 두 섬은 연결된 것으로 간주한다.
루루 왕국에 스파이로 잠입한 여러분은 국왕 루루의 신임을 얻어 다리 공사 프로젝트의 총괄을 맡게 되었다. 여러분의 목표는 루루 왕국의 국비를 낭비하는 것으로, 다른 사람들이 당신의 정체를 눈치 채지 못 하게 건설하는 다리의 개수는 최소로 하되, 사용되는 국비를 최대로 만들고자 한다. N개의 섬의 좌표가 주어질 때, 여러분이 프로젝트를 진행하는데 필요한 비용을 구하시오. 단, 여러 개의 다리를 거쳐서 이동할 수 있으면 두 섬은 연결된 것으로 간주한다.
입력 설명
첫 번째 줄에는 대한국의 섬의 개수 n이 주어진다.
두 번째 줄부터 (n+1)줄에는 섬의 좌표가 공백으로 구분되어 주어진다.
(1<=n<=1000)
(-100,000<=Mi<=100,000)
두 번째 줄부터 (n+1)줄에는 섬의 좌표가 공백으로 구분되어 주어진다.
(1<=n<=1000)
(-100,000<=Mi<=100,000)
출력 설명
프로젝트를 진행하는데 필요한 비용을 출력한다.
입력 예시 Copy
5
1 2
3 7
-1 –3
2 3
4 -8
출력 예시 Copy
28