메신저 알림 포장

문제

어느 회사의 사내 메신저는 직원이 자리를 비운 동안 쌓인 알림을 한 번에 전달하는 기능을 준비하고 있다. 전달할 알림은 총 N개이며, 발생한 순서대로 1번부터 N번까지 번호가 붙어 있다. 각 알림에는 내용을 화면에 표시하는 데 필요한 자원의 양을 나타내는 표시값이 정해져 있다. 메신저는 알림의 순서를 바꾸거나 일부 알림을 생략할 수 없다. 전달을 시작하기 전에 전체 알림을 여러 꾸러미로 나누어야 한다. 각 꾸러미에는 원래 순서에서 연속한 알림을 하나 이상 세 개 이하로 넣는다. 모든 알림은 정확히 하나의 꾸러미에 들어가야 하며, 서로 다른 꾸러미가 같은 알림을 포함할 수 없다. 꾸러미의 크기는 각각 독립적으로 정할 수 있으므로, 한 개짜리 꾸러미와 두 개짜리 꾸러미, 세 개짜리 꾸러미를 자유롭게 섞어 사용해도 된다. 알림 하나만 들어 있는 꾸러미는 별도의 포장 처리가 필요하지 않다. 이 꾸러미의 전송 비용은 그 알림의 표시값과 같다. 알림 두 개 또는 세 개가 들어 있는 꾸러미는 공통 화면을 만드는 포장 처리가 필요하다. 이때 전송 비용은 꾸러미에 속한 알림의 표시값 중 최댓값에 포장 비용 C를 더한 값이다. 표시값이 같은 알림이 여러 개 있어도 최댓값은 한 번만 더하며, C 역시 꾸러미마다 한 번만 더한다. 전체 전송 비용은 모든 꾸러미의 전송 비용을 더한 값이다. 꾸러미를 나누는 위치에 따라 전체 비용이 달라질 수 있다. 포장 비용이 크면 알림을 하나씩 보내는 편이 유리할 수도 있으므로, 가능한 경우에 항상 여러 알림을 묶어야 하는 것은 아니다. 모든 알림의 표시값과 포장 비용이 주어질 때, 전체 전송 비용의 최솟값을 구하는 프로그램을 작성한다. 최솟값을 만드는 분할이 여러 개여도 비용만 구한다.

입력

첫째 줄에 알림의 수 N과 포장 비용 C가 공백으로 구분되어 주어진다. 둘째 줄에 알림의 표시값 A_1, A_2, ..., A_N이 순서대로 주어진다. 모든 입력값은 정수이며 1≤N≤60,000, 0≤C≤9, 1≤A_i≤9다.

출력

모든 알림을 전달하는 전체 전송 비용의 최솟값을 정수 하나로 출력한다.

4 2
4 1 5 2

9

3 9
1 1 1

3

5 0
3 3 3 3 3

6

출처: Devin.KR 자체 제작