A survey team crosses a glacier crevasse by hopping across n stones numbered 0 to n-1, starting on stone 0 and finishing on stone n-1. From the current stone the team may leap forward to any stone within the next k stones (i.e. from stone i to any stone j with i < j <= i + k). Landing on stone x charges cost c[x]; the starting stone 0 and the final stone n-1 are both landed on and both charged. A cost may be negative (a cache of supplies).
Minimize the total cost of the stones landed on along a valid crossing from stone 0 to stone n-1.
Input format
Line 1: two integers n and k.
Line 2: n space-separated integers c[0] c[1] ... c[n-1].
Output format
A single integer: the minimum total cost to reach stone n-1.
Constraints
- 1 <= n <= 40
- 1 <= k <= n
- -1000 <= c[i] <= 1000