KOI 무선통신사는 직선의 통신라인 상에 기지국들을 설치하여 주변의 주요 건물들을 모두 통신범위에 포함 시키고자 한다.

각 기지국의 통신범위는 기지국을 중심으로 하고 밑변이 통신라인과 평행한 정사각형이고,

이 정사각형의 한 변의 길이를 통신폭이라 한다.

기지국들의 총 설치비용은 각 기지국의 통신폭의 합이고, 기지국의 수와는 무관하다.

평면상에 주요건물들의 위치가 주어졌을 때,

기지국들을 설치하여 모든 주요건물을 통신범위에 포함하는 최소의 총 설치비용을 구하는 프로그램을 작성하시오.

통신라인은 -축과 일치하고 건물들의 위치좌표는 정수이다.

통신라인 상에는 건물이 위치하지 않으며, 모든 건물들의 위치는 서로 다르다.

다음 그림의 예를 보면,

부분 점수는 없다.

기지국 timer 1초 memory 128MB

기지국 1초 128MB