전국 자동차 경주 대회가 매년 열리고 있다.이 대회에서는 출발지점부터 도착지점까지 거리가 워낙 멀기 때문에 경주 도중에 각 자동차는 정비소를 방문하여 정비를 받아야 한다.정비소들은 출발지점에서 도착지점으로 가는 길가에 있으며 1 번부터 차례로 번호가 부여 되어 있다.
이 대회에서는 참가하는 선수의 안전을 위하여 정비를 받지 않고는 미리 정한 거리를 초과하여 갈 수 없도록 규칙으로 정하였다.그리고 정비소마다 정비하는데 걸리는 시간이 서로 다를 수 있다. 정비소에서 정비하는데 걸리는 시간을 적게 하려고 할 때 최소 총 정비시간과 방문하는 정비소들을 구하는 프로그램을 작성하시오.
예를 들어, 아래 그림과 같이 정비소가 5 개 있고, 한번 정비를 받고 최대 140 km 를 갈수 있는 경우를 생각해 보자. 출발지점에서 정비소 1 까지의 거리는 100 km 이고, 정비소 1 을 방문하여 정비할 때 걸리는 시간은 5 분이다.
자동차가 출발지점에서 대회 규칙을 지키면서 정비소 1 , 3, 5 를 차례로 방문하여 도착지점까지 갈 수있고, 정비소 2,4 를 방문하여 갈 수도 있다. 정비소 1,3,5 를 방문하는 경우에는 16 분(=5+4+7)이 걸리고,이것은 정비소 2,4 를 방문하여 걸리는 21(=10+11)보다 총 정비 시간이 적게 걸린다.
입력 140 5 100 30 100 40 50 60 5 10 4 11 7 출력 16
출처:koi 초등부 기출