183. Painting the balls
time limit per test: 0.25
sec.
memory limit per test: 4096
KB
input: standard input
output: standard output
Petya puts the N white balls in a line and now he wants to paint some of them in black, so that at least two black balls could be found among any M successive balls. Petya knows that he needs Ci milliliters of dye exactly to paint the ith ball. Your task is to find out for Petya the minimum amount of dye he will need to paint the balls.
Input
The first line contains two integer numbers N and M (2<=N<=10000, 2<=M<=100, M<=N). The second line contains N integer numbers C1, C2, ..., CN (1<=Ci<=10000).
Output
Output only one integer number  the minimum amount of dye Petya will need (in milliliters).
Sample test(s)
Input
6 3
1 5 6 2 1 3
Output
9
Note
Example note: 1, 2, 4, 5 balls must be painted.
Author:  Andrew V. Lazarev

Resource:  ACM International Collegiate Programming Contest 20032004
NorthEastern European Region, Southern Subregion

Date:  2003 October, 9

Server time: 20171121 05:19:00  Online Contester Team © 2002  2016. All rights reserved. 

