게임회사 사장인 쟁구가 만든 어떤 게임의 이름은 공항 타이쿤이다. 게임은 아주 간단하며, 다음과 같다.

긴 직선 모양의 정올국에 몇 개의 공항을 세우려고 한다. 정올국을 수직선으로 생각했을 때, 각 정수 좌표들에는 주요 도시들이 위치해 있다. 이 주요 도시들 중 어느 곳에든지 공항을 세울 수 있다. 비행기들이 이륙 후 바로 착륙할 때 최소 d의 거리가 필요하므로, 두 공항 사이의 거리가 d 이상이어야만 두 공항 사이를 비행기로 이동할 수 있다.

게임 내에서 2001년에 하나의 공항을 정올국에 가지고 시작한다. 다음 해부터, 매 해마다 새로운 공항이 어떤 위치에 세워진다. 이 때 어떤 두 공항 (a,b)를 고르더라도 a에서 b로 직접 또는 다른 공항을 경유해서 비행기로 여행이 가능해야 한다. 이 조건을 만족시키지 못한다면, 공항을 다른 위치로 옮겨야 한다. 원래 공항의 위치를 x, 옮기고자 하는 위치를 y라 할때 공항을 다른 위치로 이동시키는데는 |x-y|만큼의 값이 든다. 한 해마다, 공항을 최소비용으로 옮겨야만 다음 스테이지인 다음 해로 넘어갈 수 있다. 다음 해로 넘어가면, 플레이어가 이전에 옮겼던 공항들은 전부 원위치로 돌아간다. n개의 스테이지(즉 n년)을 넘기면 클리어한다.

매 해마다 추가되는 공항의 위치가 주어졌을 때, 그 해의 공항을 옮기는 최소 비용을 각각 구하는 프로그램을 작성하라.

[입력예2 보충설명 그림]

#3193 upload 56 done 5 how_to_reg 2

공항 타이쿤 timer 3s memory 256MB

#3193

공항 타이쿤 3s 256MB