Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Cashback

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputSince you are the best Wraith King, Nizhniy Magazin «Mir» at the centre of Vinnytsia is offering you a discount.

You are given an array *a* of length *n* and an integer *c*.

The value of some array *b* of length *k* is the sum of its elements except for the smallest. For example, the value of the array [3, 1, 6, 5, 2] with *c* = 2 is 3 + 6 + 5 = 14.

Among all possible partitions of *a* into contiguous subarrays output the smallest possible sum of the values of these subarrays.

Input

The first line contains integers *n* and *c* (1 ≤ *n*, *c* ≤ 100 000).

The second line contains *n* integers *a*_{i} (1 ≤ *a*_{i} ≤ 10^{9}) — elements of *a*.

Output

Output a single integer — the smallest possible sum of values of these subarrays of some partition of *a*.

Examples

Input

3 5

1 2 3

Output

6

Input

12 10

1 1 10 10 10 10 10 10 9 10 10 10

Output

92

Input

7 2

2 3 6 4 5 7 1

Output

17

Input

8 4

1 3 4 5 5 3 4 1

Output

23

Note

In the first example any partition yields 6 as the sum.

In the second example one of the optimal partitions is [1, 1], [10, 10, 10, 10, 10, 10, 9, 10, 10, 10] with the values 2 and 90 respectively.

In the third example one of the optimal partitions is [2, 3], [6, 4, 5, 7], [1] with the values 3, 13 and 1 respectively.

In the fourth example one of the optimal partitions is [1], [3, 4, 5, 5, 3, 4], [1] with the values 1, 21 and 1 respectively.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/17/2018 04:54:06 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|