기지국
시간 제한2초메모리 제한128 MB
x축이 아닌 평면 위 점들을 x축 중심의 정사각형들로 모두 덮을 때, 정사각형 변 길이 합의 최소값을 구합니다.
문제
한 무선통신사는 직선 모양의 통신라인 위에 기지국들을 설치하여, 평면 위의 모든 주요 건물이 적어도 하나의 통신범위 안에 들어가도록 하려 한다.
통신라인은 x축과 일치한다. 각 기지국은 통신라인 위의 한 점에 설치되며, 그 기지국의 통신범위는 기지국을 중심으로 하고 변들이 좌표축과 평행한 정사각형이다. 이 정사각형의 한 변의 길이를 그 기지국의 통신폭이라고 한다.
총 설치비용은 설치한 모든 기지국의 통신폭의 합이며, 설치한 기지국의 개수 자체에는 비용이 붙지 않는다.
모든 주요 건물의 좌표가 주어질 때, 모든 건물을 통신범위에 포함시키는 최소 총 설치비용을 구하라. 건물 좌표는 정수이고, 통신라인 위에는 건물이 없다. 모든 건물의 위치는 서로 다르다.
입력
첫째 줄에 건물의 개수 N이 주어진다. (1 <= N <= 10,000)
다음 N개의 줄에는 한 줄에 한 건물의 x좌표와 y좌표가 공백으로 구분되어 주어진다. 각 좌표는 절댓값이 1,000,000 이하인 정수이다.
출력
첫째 줄에 가능한 최소 총 설치비용, 즉 설치한 기지국들의 통신폭 합의 최솟값을 출력한다.