Since 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*$.

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.