KOI 택배 회사는 물품을 빠르고 정확하게 배송하기로 유명하다.

본점으로 수집된 물품은 각각 지정된 지점으로 배송되는데, 본점은 고속도로가 시작하는 곳에 있고,

지점들은 1번 부터 10,000번까지 번호 순서대로 고속도로를 따라 일정한 간격으로 놓여 있다.

물품을 옮기는 데는 트럭과 헬리콥터를 이용하는 두 가지 방법이 있다.

트럭은 본점에서 지점으로 또는 지점에서 다른 지점으로 물품을 옮기는 데 사용되고,

헬리콥터는 본점에서 지점으로 물품을 옮기는데 사용된다.

트럭이 한 물품을 운반하는데 비용은 그 물품의 운송 거리에 비례하고,

헬리콥터는 물품의 개수와 운송 거리와는 상관없이 비용이 일정하다.

트럭으로는 한 번에 하나의 물품을 운송할 수 있으나, 헬리콥터는 운송할 수 있는 물품의 개수는 제한이 없다.

항상 충분한 수의 트럭과 헬리콥터가 준비되어 있다고 가정한다.

예를 들어, 본점에 10번, 40번, 30번, 50번, 10번 지점으로 옮겨야 하는 5개의 물품이 접수되었는데,

물품 하나를 트럭으로 한 지점 간격 옮기는 데는 10만큼의 비용이 들고,

헬리콥터를 한 번 이용하는 데는 개수나 거리에 상관없이 200만큼의 비용이 든다고 하자.

5개의 물품을 모두 트럭을 이용해서 옮기면,

10x10 + 40x10 + 30x10 + 50x10 + 10x10 = 1400

으로 총 1400만큼의 비용이 든다.

하지만 10번 지점으로 가야하는 두 물품은 트럭으로 옮기고,

나머지 세 물품은 한꺼번에 40번 지점으로 헬리콥터를 이용해서 옮기면 40번 지점으로 갈 물품은 목적 지점에 도착되었고,

이어 30번 지점과 50번 지점으로 갈 물품을 40번 지점에서 각각 트럭을 이용하여 옮기면,

10x10 + 10x10 + 200 + 10x10 + 10x10 = 600

으로 총 600만큼의 비용이 든다.

배송할 물품의 총 개수와, 각 물품의 목적 지점, 트럭과 헬리콥터 사용 비용이 주어질 때,

모든 물품을 목적 지점으로 옮기는데 드는 총 비용의 최솟값을 구하는 프로그램을 작성하시오.

택배 timer 1s memory 128MB

택배 1s 128MB