두 번 묶어 타기

문제

공유 자전거를 이용하는 다온은 앞으로 자전거를 탈 계획을 시간순으로 정리했다. 계획에는 모두 N번의 이용이 있으며, 각 이용은 자전거를 빌린 뒤 반납하는 한 번의 활동이다. 다온은 모든 이용을 계획한 순서대로 마쳐야 한다. 이용을 생략하거나 순서를 바꿀 수는 없다. 이 공유 자전거의 요금은 출발 구역에 따라 달라진다. i번째 이용에 일반 이용권을 사용하면 A_i원을 낸다. 일반 이용권 한 장은 해당 이용 한 번에만 사용할 수 있으며, 다른 이용으로 나누어 사용할 수 없다. 다온은 일반 이용권 대신 두 번 이용권을 살 수도 있다. 두 번 이용권의 가격은 어느 구역에서 출발하든 K원으로 같다. 두 번 이용권 한 장은 계획에서 바로 이어지는 두 번의 이용을 함께 결제한다. 즉, 어떤 i에 대해 i번째 이용과 i+1번째 이용에 사용할 수 있다. 두 이용 사이의 시간 간격은 이용권 사용에 영향을 주지 않는다. 그러나 중간에 다른 이용을 건너뛰어 묶을 수는 없다. 예를 들어 첫 번째 이용과 세 번째 이용을 두 번 이용권 한 장으로 결제할 수는 없다. 각 이용은 반드시 이용권 하나에만 포함되어야 한다. 따라서 두 번 이용권끼리 같은 이용을 공유하거나, 두 번 이용권으로 결제한 이용에 일반 이용권을 추가로 사용할 수 없다. 두 번 이용권의 절반만 사용하거나 계획에 없는 이용을 추가하는 것도 허용되지 않는다. 두 종류의 이용권은 필요한 만큼 살 수 있으며, 두 번 이용권을 전혀 사지 않아도 된다. 다온은 이용권을 미리 정해진 순서로 살 필요 없이 전체 계획을 보고 결제 방법을 선택한다. 모든 이용을 결제하는 데 필요한 총금액의 최솟값을 구한다. 최소 금액을 만드는 방법이 여러 개여도 금액만 구하면 된다.

입력

첫째 줄에 이용 횟수 N과 두 번 이용권의 가격 K가 공백으로 구분되어 주어진다.
둘째 줄에 일반 이용권 가격 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
모든 입력값은 정수이며, 1 ≤ N ≤ 100,000, 1 ≤ K ≤ 18, 1 ≤ A_i ≤ 9이다.

출력

모든 이용을 결제하는 데 필요한 총금액의 최솟값을 원 단위의 정수 하나로 출력한다. 일반 이용권으로 모든 이용을 결제할 수 있으므로 답은 항상 존재한다.

5 7
3 6 2 8 4

16

4 10
1 2 3 4

10

1 1
9

9

출처: Devin.KR 자체 제작