No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 4096 KB

memory limit per test: 4096 KB

input: standard input

output: standard output

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).

Input

6 3

1 5 6 2 1 3

1 5 6 2 1 3

Output

9

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 |

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Oct/24/2019 03:39:49 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|