두 곡 묶음 이용권

문제

음악 스트리밍 서비스에서 사용자가 재생할 곡 N개를 순서대로 예약했다. 같은 노래가 여러 번 예약되어 있어도 각 재생 위치는 서로 다른 예약으로 취급한다. 사용자는 예약 순서를 바꾸거나 곡을 건너뛸 수 없으며, 모든 예약을 정확히 한 번씩 결제해야 한다. i번째 예약을 단독 이용권으로 결제하는 비용은 A_i포인트다. 서비스는 단독 이용권 외에 두 곡 묶음 이용권을 제공한다. 이 이용권 하나는 예약 목록에서 서로 이웃한 두 위치를 함께 결제한다. i번째와 i+1번째 예약을 묶으면 두 단독 비용 중 큰 값에 고정 수수료 C를 더한 max(A_i, A_{i+1})+C포인트를 낸다. 수수료는 묶음 이용권마다 한 번씩 붙는다. 묶음 이용권의 비용이 단독 이용권 두 장의 합보다 비쌀 수도 있으며, 이용권을 반드시 묶어서 살 필요는 없다. 한 예약을 두 이용권에 중복으로 포함할 수 없다. 예를 들어 2번째와 3번째 예약을 하나의 묶음으로 결제했다면, 1번째와 2번째 예약을 또 다른 묶음으로 결제할 수 없다. 반면 1번째와 2번째 예약을 묶고 3번째와 4번째 예약을 별도로 묶는 것은 가능하다. 목록의 마지막 예약과 첫 번째 예약은 서로 이웃한 것으로 보지 않는다. 사용자는 단독 이용권과 묶음 이용권을 원하는 개수만큼 구매할 수 있다. 이용권 구매 순서에 따른 추가 할인이나 비용은 없다. 모든 예약을 빠짐없이 결제하는 방법 중 총비용의 최솟값을 구한다. 최솟값을 만드는 방법이 여러 개이면 그 비용만 출력하며, 실제 이용권 구성은 출력하지 않는다.

입력

첫째 줄에 정수 N과 C가 주어진다. 1≤N≤30,000이고 0≤C≤1,000이다. 둘째 줄에 정수 A_1, A_2, …, A_N이 주어진다. 모든 i에 대해 1≤A_i≤1,000이다.

출력

모든 예약을 결제하는 데 필요한 최소 총비용을 정수로 한 줄에 출력한다.

4 1
6 2 5 7

15

3 0
3 8 7

11

1 10
4

4

출처: Devin.KR 자체 제작