달려달려

어제와 그제, 학생들은 단체 달리기를 두 번이나 했다. 힘든 훈련 덕분에 학생들은 운동장을 정확히 N분 동안 돌 수 있도록 달리기와 휴식을 조절할 수 있게 되었다.

앞으로 N분 동안, 매 분마다 학생들은 달리거나 쉴 수 있다. 피로도는 처음에 0이다. 1분 동안 달리면 피로도가 1 증가하고, 1분 동안 쉬면 피로도가 1 감소한다. 피로도가 0일 때 쉬면 피로도는 0으로 유지된다. 피로도는 M을 초과할 수 없으므로, 피로도가 M인 상태에서는 달릴 수 없다.

i번째 분에 달리면 D_i만큼의 거리를 이동한다. 이는 i분 동안 달렸다는 뜻이 아니라, 전체 시간 중 i번째 1분을 달렸을 때의 거리이다. 한 번 쉬기 시작했을 때 피로도가 0보다 크다면, 피로도가 0이 될 때까지 계속 쉬어야 한다.

달리기가 끝나는 N분 시점에도 피로도는 반드시 0이어야 한다. N분 동안 이동할 수 있는 최대 거리를 구하라.

첫째 줄에 운동 시간 N (1 ≤ N ≤ 10000)과 최대 피로도 M (1 ≤ M ≤ 500)이 주어진다. 다음 N개의 줄에는 i번째 분에 달렸을 때 이동할 수 있는 거리 D_i (0 ≤ D_i ≤ 10000)가 1번부터 N번 순서대로 주어진다.

첫째 줄에 조건을 모두 만족하면서 이동할 수 있는 최대 거리를 출력한다.

첫 번째 분에 5만큼 달리고, 두 번째 분에는 쉬어서 피로도를 0으로 만든다. 세 번째 분에 4만큼 더 달린 뒤, 네 번째와 다섯 번째 분에는 쉬면 총 거리는 9가 된다.