처리 묶음의 경계

문제

한 게임 서버에 처리할 작업 N개가 도착 순서대로 쌓여 있다. 각 작업에는 1부터 9까지의 정수로 표시한 부하 등급이 있다. 서버 관리자는 작업을 하나씩 실행하는 대신, 연속한 작업 몇 개를 하나의 처리 묶음으로 만들어 실행하려고 한다. 작업의 순서는 바꿀 수 없으며, 모든 작업은 정확히 하나의 묶음에 포함되어야 한다. 서버의 실행 장치는 한 묶음에 작업을 1개 이상 3개 이하로 넣을 수 있다. 같은 묶음 안의 작업들은 동시에 실행되므로, 실제 작업을 수행하는 데 필요한 시간은 그 묶음에 속한 작업들의 부하 등급 중 최댓값과 같다. 여기에 묶음을 실행할 때마다 준비 시간 K가 추가된다. 따라서 어떤 묶음의 부하 등급이 2, 8, 4라면 그 묶음의 처리 시간은 K+8이다. 작업이 하나뿐인 묶음에도 준비 시간은 똑같이 추가된다. 서로 다른 묶음들은 앞에서부터 하나씩 차례로 실행되며, 두 묶음을 동시에 실행할 수 없다. 전체 처리 시간은 모든 묶음의 처리 시간을 더한 값이다. 묶음 사이에 추가로 드는 시간은 없고, 한 작업을 여러 묶음으로 나누거나 작업을 생략할 수 없다. 관리자가 정할 수 있는 것은 이웃한 두 작업 사이에서 묶음을 끊을지 여부뿐이다. 묶음에 작업을 많이 넣으면 준비 시간을 아낄 수 있지만, 큰 부하 등급의 작업들이 서로 다른 묶음에 들어가면 전체 처리 시간이 늘어날 수 있다. 따라서 항상 앞에서부터 세 작업씩 묶는 방법이 최선인 것은 아니다. 주어진 작업을 모두 처리하는 데 필요한 전체 시간의 최솟값을 구한다. 최솟값을 만드는 분할이 여러 개라면 그 값만 출력하며, 분할 방법은 출력하지 않는다. 작업을 하나씩 묶는 방법이 항상 가능하므로 처리할 수 없는 입력은 없다.

입력

첫째 줄에 작업 수 N과 묶음마다 드는 준비 시간 K가 공백으로 구분되어 주어진다. N과 K는 정수이며 1 ≤ N ≤ 200,000, 0 ≤ K ≤ 1,000,000,000이다.
둘째 줄에 길이가 정확히 N인 문자열 S가 주어진다. S는 문자 '1'부터 '9'로만 이루어져 있으며, i번째 문자가 나타내는 정수가 도착 순서상 i번째 작업의 부하 등급이다. 문자열 안에는 공백이 없다.

출력

모든 작업을 처리하는 데 필요한 전체 시간의 최솟값을 정수 하나로 출력한다.

6 1
119911

14

1 0
7

7

5 2
81918

21

출처: Devin.KR 자체 제작