Problem: You are given array a_1, a_2, ..., a_n. You need to split it into k subsegments (so every element is included in exactly one subsegment).

The weight of a subsegment a_l, a_{l+1}, ..., a_r is equal to (r - l + 1) ⋅ max_{l ≤ i ≤ r}(a_i). The weight of a partition is a total weight of all its segments.

Find the partition of minimal weight.

Input

The first line contains two integers n and k (1 ≤ n ≤ 2 ⋅ 10^4, 1 ≤ k ≤ min(100, n)) — the length of the array a and the number of subsegments in the partition.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ 2 ⋅ 10^4) — the array a.

Output

Print single integer — the minimal weight among all possible partitions.

Examples

Input


4 2
6 1 7 4


Output


25


Input


4 3
6 1 7 4


Output


21


Input


5 4
5 1 5 1 5


Output


21

Note

The optimal partition in the first example is next: 6 1 7 \bigg| 4.

The optimal partition in the second example is next: 6 \bigg| 1 \bigg| 7 4.

One of the optimal partitions in the third example is next: 5 \bigg| 1 5 \bigg| 1 \bigg| 5.

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const int N = 20010, K = 110;
int dp[K][N], cur, n, arr[N], last[N], k, cnt[4 * N];
vector<pair<int, pair<int, int> > > seg[4 * N];
stack<int> st;
int mx[N];
int tmpp;
const int sq = 60;
int Last;
pair<int, pair<int, int> > bucket[350][70];
int cnt2[N], change[N], sz[N];
bool bad[N];
inline int get(int a1, int b1, int a2, int b2) {
  if (a1 == a2) {
    if (b2 <= b1) return -1000000000;
    return 1000000000;
  }
  tmpp = (b2 - b1) / (a1 - a2) - 1;
  while ((long long)a2 * tmpp + (long long)b2 >
         (long long)a1 * tmpp + (long long)b1)
    tmpp++;
  return tmpp;
}
inline int get2(int a1, int b1, int a2, int b2) {
  if (a1 == a2) {
    if (b2 <= b1) return 1000000000;
    return -1000000000;
  }
  tmpp = (b2 - b1) / (a1 - a2) + 1;
  while ((long long)a2 * tmpp + (long long)b2 >
         (long long)a1 * tmpp + (long long)b1)
    tmpp--;
  return tmpp;
}
void build_bucket(int i) {
  bad[i] = false;
  sz[i] = 0;
  cnt2[i] = 0;
  int tmp1;
  for (int j = min(n - 1, (i + 1) * sq - 1); j >= max(Last, i * sq); j--) {
    while (sz[i] > 0) {
      tmp1 = get2(bucket[i][sz[i] - 1].second.first,
                  bucket[i][sz[i] - 1].second.second, -mx[j],
                  dp[cur + 1][j + 1] + (j + 1) * mx[j]);
      if (tmp1 >= bucket[i][sz[i] - 1].first)
        sz[i]--;
      else
        break;
    }
    if (sz[i] == 0)
      tmp1 = 1000000000;
    else
      tmp1 = get2(bucket[i][sz[i] - 1].second.first,
                  bucket[i][sz[i] - 1].second.second, -mx[j],
                  dp[cur + 1][j + 1] + (j + 1) * mx[j]);
    bucket[i][sz[i]++] = (make_pair(
        tmp1, make_pair(-mx[j], dp[cur + 1][j + 1] + (j + 1) * mx[j])));
  }
  change[i] = -1;
}
inline int getmin_in_bucket(int i, int val) {
  while (cnt2[i] < sz[i] && bucket[i][cnt2[i]].first >= val) cnt2[i]++;
  return bucket[i][cnt2[i] - 1].second.first * val +
         bucket[i][cnt2[i] - 1].second.second;
}
void build(int s, int e, int idx) {
  seg[idx].clear();
  cnt[idx] = 0;
  if (s == e) {
    seg[idx].push_back(
        make_pair(-1000000000, make_pair(s + 1, dp[cur][s + 1])));
    return;
  }
  build(s, ((s + e) >> 1), (idx << 1));
  build(((s + e) >> 1) + 1, e, (idx << 1) + 1);
  int i = 0, tmp1;
  seg[idx].push_back(make_pair(-1000000000, make_pair(e + 1, dp[cur][e + 1])));
  for (int i = e - 1; i >= s; i--) {
    while ((int)seg[idx].size() > 0) {
      tmp1 = get(seg[idx].back().second.first, seg[idx].back().second.second,
                 i + 1, dp[cur][i + 1]);
      if (tmp1 <= seg[idx].back().first)
        seg[idx].pop_back();
      else
        break;
    }
    if ((int)seg[idx].size() == 0)
      tmp1 = -1000000000;
    else
      tmp1 = get(seg[idx].back().second.first, seg[idx].back().second.second,
                 i + 1, dp[cur][i + 1]);
    seg[idx].push_back(make_pair(tmp1, make_pair(i + 1, dp[cur][i + 1])));
  }
}
int l, r, val;
pair<int, int> getmin(int s, int e, int idx) {
  if (s > r || e < l) return make_pair(1000000000, 1000000000);
  if (s >= l && e <= r) {
    while (cnt[idx] < (int)seg[idx].size() && seg[idx][cnt[idx]].first <= val)
      cnt[idx]++;
    return make_pair(seg[idx][cnt[idx] - 1].second.first * val +
                         seg[idx][cnt[idx] - 1].second.second,
                     seg[idx][cnt[idx] - 1].second.first - 1);
  }
  return min(getmin(s, (s + e) >> 1, (idx << 1)),
             getmin(((s + e) >> 1) + 1, e, (idx << 1) + 1));
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++) {
    scanf("%d", &arr[i]);
  }
  for (int i = n - 1; i >= 0; i--) {
    while ((int)st.size() > 0) {
      if (arr[i] >= arr[(int)st.top()])
        st.pop();
      else
        break;
    }
    if ((int)st.size() == 0)
      last[i] = n - 1;
    else
      last[i] = st.top() - 1;
    st.push(i);
  }
  cur = k;
  for (int i = 0; i < n; i++) dp[cur][i] = 1000000000;
  build(0, n - 1, 1);
  int tmp2, tmp3, tmp4, tmp1, idx = 0;
  pair<int, int> tmp5;
  for (cur = k - 1; cur >= 0; cur--) {
    idx = 0;
    Last = n;
    for (int i = n - 1; i >= 0; i--) {
      Last--, dp[cur][i] = 1000000000;
      if (i == n - 1) {
        dp[cur][i] = arr[i] + dp[cur + 1][i + 1];
        dp[cur][i] = min(dp[cur][i], 1000000000);
        mx[i] = arr[i];
        build_bucket(i / sq);
        change[i / sq] = -1;
        continue;
      }
      l = i, r = last[i], val = arr[i];
      tmp1 = getmin(0, n - 1, 1).second;
      for (int j = l / sq; j <= r / sq; j++) {
        if (min(n - 1, (j + 1) * sq - 1) <= r) {
          bad[j] = true;
          change[j] = val;
        } else {
          bad[j] = false;
          for (int k = j * sq; k <= r; k++) mx[k] = val;
          if (change[j] != -1) {
            for (int k = r + 1; k < min(n, (j + 1) * sq); k++)
              mx[k] = change[j];
          }
          r = j * sq - 1;
          build_bucket(j);
          break;
        }
      }
      if (tmp1 <= r) {
        bad[tmp1 / sq] = false;
        for (int j = max(Last, (tmp1 / sq) * sq);
             j < min(n, ((tmp1 / sq) + 1) * sq); j++) {
          mx[j] = val;
        }
        build_bucket(tmp1 / sq);
      }
      for (int j = i / sq; j <= (n - 1) / sq; j++) {
        if (!bad[j]) dp[cur][i] = min(dp[cur][i], getmin_in_bucket(j, i));
      }
    }
    dp[cur][n] = 1000000000;
    build(0, n - 1, 1);
  }
  cout << dp[0][0] << endl;
  return 0;
}