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 <image> 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 ai (1 ≤ ai ≤ 109) — 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.
#include <bits/stdc++.h>
using namespace std;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long n, c;
  cin >> n >> c;
  long long arr[n];
  for (long long i = 0; i < n; i++) cin >> arr[i];
  if (c == 1) {
    cout << 0;
    return 0;
  }
  long long dp[n];
  for (long long i = 0; i < n; i++) dp[i] = 10000000000000000;
  dp[0] = arr[0];
  map<long long, long long> ma;
  ma[arr[0]] = 1;
  long long sum = arr[0];
  for (long long i = 1; i < n; i++) {
    sum += arr[i];
    ma[arr[i]]++;
    if (i == c - 1) {
      dp[i] = min(dp[i], sum - (ma.begin())->first);
    }
    if (i >= c) {
      sum -= arr[i - c];
      ma[arr[i - c]]--;
      if (ma[arr[i - c]] == 0) ma.erase(arr[i - c]);
      long long temp = sum - (ma.begin())->first;
      dp[i] = min(dp[i], dp[i - c] + temp);
    }
    dp[i] = min(dp[i - 1] + arr[i], dp[i]);
  }
  cout << dp[n - 1];
  return 0;
}
