강 건너기

농부 존은 소 $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$분입니다.