183. Painting the balls
time limit per test: 0.25
memory limit per test: 4096
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 i-th ball. Your task is to find out for Petya the minimum amount of dye he will need to paint the balls.
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 only one integer number - the minimum amount of dye Petya will need (in milliliters).
1 5 6 2 1 3
Example note: 1, 2, 4, 5 balls must be painted.
|Author:||Andrew V. Lazarev
|Resource:||ACM International Collegiate Programming Contest 2003-2004
North-Eastern European Region, Southern Subregion
|Date:||2003 October, 9
|Server time: 2017-11-21 05:19:00||Online Contester Team © 2002 - 2016. All rights reserved.|