좌표평면 위에 서로 다른 개의 정수점이 주어진다. 두 점 과 사이의 거리는 맨해튼 거리 이다.
주어진 점 가운데 정확히 하나를 골라 원하는 정수점으로 옮길 수 있다. 옮긴 뒤의 개 점을 정점으로 하는 최소 스패닝 트리의 가중치 합을 가능한 한 작게 만들려고 한다.
가능한 최소 가중치 합을 구하여라. 고른 점을 원래 위치로 옮기거나 다른 점과 같은 좌표로 옮겨도 된다.
입력은 다음과 같은 형식으로 주어진다.
case case
각 테스트 케이스마다 가능한 최소 맨해튼 MST 가중치 합을 한 줄에 출력한다.
의 점을 로 옮기면 가중치가 각각 인 두 간선으로 스패닝 트리를 만들 수 있다.
각 케이스는 다음과 같은 형식으로 주어진다.
