강 건너기

면접 대비

시간 제한1초메모리 제한128 MB

요약

소 N마리를 순서대로 여러 무리로 나눠 건널 때, 각 무리의 건너는 시간은 M에 누적 추가 시간을 더한 값이고 마지막을 제외한 무리마다 M분의 귀환 시간이 더해질 때, 총 시간의 최솟값을 구한다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 누적 합, 배열, 그리디
정답자: 아직 제출이 없습니다

문제

농부 존은 소 $N$ 마리( $1 \le N \le 2500$ )를 강 건너편으로 옮기려고 합니다. 뗏목은 하나뿐이며, 강을 건널 때마다 존이 반드시 함께 타야 합니다.

뗏목에 소를 태울수록 속도가 느려집니다. 존 혼자 타면 뗏목은 $M$ 분( $1 \le M \le 1000$ )에 강을 건넙니다. 소를 한 마리씩 태울 때, $i$ 번째로 태우는 소는 $i-1$ 마리를 태웠을 때보다 $M_i$ 분( $1 \le M_i \le 1000$ )이 더 걸리게 만듭니다. 즉 소 $k$ 마리를 태운 뗏목은 $M + M_1 + M_2 + \cdots + M_k$ 분에 강을 건넙니다. 소들은 서로 구분되지 않으며, 함께 타는 마릿수만 중요하고, 한계 비용은 $M_1, M_2, \ldots$ 순서대로 적용됩니다.

존은 여러 번에 나누어 소를 실어 나를 수 있습니다. 마지막을 제외한 각 왕복에서는 존이 혼자 돌아오며, 이때도 $M$ 분이 걸립니다. 돌아오는 시간을 포함하여 모든 소 $N$ 마리를 건너편으로 옮기는 데 걸리는 최소 시간을 구하세요.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $M$ .
둘째 줄부터 $N+1$ 번째 줄까지: $i+1$ 번째 줄에 정수 $M_i$ 가 하나씩 주어집니다.

출력

모든 소를 건너편으로 옮기는 최소 시간을 한 줄에 출력합니다.

힌트

소가 다섯 마리 있고 건너는 시간이 다음과 같다고 합시다. 존 혼자면 10분, 소 한 마리와 함께면 13분, 두 마리 17분, 세 마리 23분, 네 마리 123분, 다섯 마리 모두 124분입니다. 한 가지 좋은 방법은 소 세 마리를 태워 건너고(23분), 혼자 돌아온 뒤(10분), 남은 두 마리를 태워 건너는 것(17분)으로, 합계 $23 + 10 + 17 = 50$ 분입니다.

예제2

예제 1
입력
```
5 10
3
4
6
100
1
```
예상 출력
```
50
```
예제 2
입력
```
1 10
5
```
예상 출력
```
15
```