이웃한 두 비행의 묶음권

문제

한 여행자는 여러 도시를 차례로 방문하는 여행을 준비하고 있다. 여행 일정에는 총 N번의 비행이 있으며, 실제로 탑승할 순서에 따라 1번부터 N번까지 번호가 붙어 있다. 출발 시각과 방문 도시는 이미 정해져 있으므로 비행 순서를 바꾸거나 일부 비행을 생략할 수 없다. 여행자는 이 일정 전체에 사용할 항공권을 가장 적은 비용으로 구매하려고 한다. 각 비행에는 그 비행 한 번에만 사용할 수 있는 개별 항공권이 있다. i번 비행의 개별 항공권 가격은 A_i다. 이와 별도로 여행 일정에서 번호가 연속한 두 비행을 함께 처리하는 묶음권도 판매한다. 묶음권 한 장의 가격은 어느 두 비행을 고르든 C로 같다. 예를 들어 3번 비행과 4번 비행에는 묶음권 한 장을 사용할 수 있지만, 3번 비행과 5번 비행에는 사용할 수 없다. 묶음권 한 장은 선택한 두 비행을 모두 담당한다. 각 비행에는 개별 항공권 또는 묶음권 중 정확히 하나만 배정해야 한다. 따라서 2번과 3번 비행에 묶음권을 사용했다면, 3번과 4번 비행에 다른 묶음권을 함께 사용할 수 없다. 개별 항공권과 묶음권은 필요한 만큼 구매할 수 있으며, 묶음권을 반드시 구매해야 하는 것은 아니다. 첫 비행과 마지막 비행은 일정에서 서로 이웃한 것으로 취급하지 않는다. 항공권 가격은 모두 정수이며, 추가 수수료나 할인은 없다. 묶음권 가격이 그 두 비행의 개별 항공권 가격 합보다 비쌀 수도 있으므로, 사용할 묶음권의 위치를 적절히 정해야 한다. 모든 비행을 정확히 한 번씩 담당하도록 항공권을 구매하는 최소 총비용을 구한다. 같은 최소 비용을 만드는 구매 방법이 여러 개라면 비용만 출력한다. 모든 비행의 개별 항공권을 살 수 있으므로 구매 방법은 항상 존재한다.

입력

첫째 줄에 정수 N과 C가 공백으로 구분되어 주어진다. 둘째 줄에 정수 A_1, A_2, ..., A_N이 공백으로 구분되어 주어진다.
1 ≤ N ≤ 50,000, 1 ≤ C ≤ 1,998이다. 모든 i에 대해 1 ≤ A_i ≤ 999이다.

출력

모든 비행을 정확히 한 번씩 담당하는 항공권의 최소 총비용을 정수 하나로 출력한다.

5 9
8 3 7 6 2

20

3 15
2 3 4

9

1 1
999

999

출처: Devin.KR 자체 제작