Sane's Monthly Algorithms Challenge: October 2008

Hopscotch is a simple game which can be played with a group or family or individually. Diana has been playing the game for years and is easily the best Hopscotch player on the playground. Her friends have decided to challenge her title by inventing a complicated version of Hopscotch called Jumpscotch.

In Jumpscotch, a single row of squares is drawn along the ground and a positive integer is drawn inside each square. Starting on the first square, Diana must jump from square to square and finish on the last square. Afterwards, her 'score' is the sum of all numbers which she has touched. The objective of Jumpscotch is to get a lower score than your opponent.

Diana knows that she is only strong enough to hop a certain distance ~D~. She is also smart enough to know that with this limitation, the best 'path' is not always obvious. Diana wants your help in determining the best path, given each square's value and her maximum hopping distance.

Input Specification

On the first line, the integers ~N~ ~(1 \le N \le 1\,000\,000)~ and ~D~ ~(1 \le D \le 10)~.
There will be one test case where Diana has superhuman strength and ~D = 5\,000~ while ~N = 1\,000\,000~.

The next ~N~ lines that follow have positive integers ~\le 1\,000~, representing the number drawn inside each square. These lines are listed, in order, from start to finish.

Output Specification

On a single line, output the smallest possible score that Diana can obtain.

Sample Input 1

12 3
1
4
2
6
5
1
1
8
7
3
1
2

Sample Output 1

10