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 = 2e4 + 3, M = N << 5;
int u[N], v[N], *f = u, *g = v, a[N], rt[N], id, K[N], b[N], lc[M], rc[M], s[M],
                st[N];
void upd(int k, int l, int r, int t) {
  if (l == r) {
    if ((b[t] + a[t] * (l)) < (b[s[k]] + a[s[k]] * (l))) s[k] = t;
    return;
  }
  int m = l + r >> 1;
  if ((b[t] + a[t] * (m)) < (b[s[k]] + a[s[k]] * (m))) swap(t, s[k]);
  (b[t] + a[t] * (l)) < (b[s[k]] + a[s[k]] * (l))
      ? upd(lc[k] = (lc[++id] = lc[lc[k]], rc[id] = rc[lc[k]], s[id] = s[lc[k]],
                     id),
            l, m, t)
      : upd(rc[k] = (lc[++id] = lc[rc[k]], rc[id] = rc[rc[k]], s[id] = s[rc[k]],
                     id),
            m + 1, r, t);
}
int qry(int k, int l, int r, int d) {
  if (l == r || !k) return (b[s[k]] + a[s[k]] * (d));
  int m = l + r >> 1;
  return min((b[s[k]] + a[s[k]] * (d)),
             d <= m ? qry(lc[k], l, m, d) : qry(rc[k], m + 1, r, d));
}
struct H {
  deque<int> d;
  void mg(H& h) {
    int t = h.d.size() - 1;
    if (h.d.size() > d.size()) {
      for (int x : d) {
        while (t && (g[x] - g[h.d[t]]) * 1ll * (h.d[t] - h.d[t - 1]) <=
                        (g[h.d[t]] - g[h.d[t - 1]]) * 1ll * (x - h.d[t]))
          --t, h.d.pop_back();
        ++t, h.d.push_back(x);
      }
      swap(h.d, d);
    } else {
      for (int x; ~t; --t) {
        x = h.d[t];
        while (d.size() > 1 && (g[d[0]] - g[x]) * 1ll * (d[1] - d[0]) >=
                                   (g[d[1]] - g[d[0]]) * 1ll * (d[0] - x))
          d.pop_front();
        d.push_front(x);
      }
    }
  }
  int qry(int k) {
    int l = 1, r = d.size() - 1, m;
    while (l <= r)
      if (m = l + r >> 1, g[d[m]] - g[d[m - 1]] < k * 1ll * (d[m] - d[m - 1]))
        l = m + 1;
      else
        r = m - 1;
    return g[d[l - 1]] - (d[l - 1] - 1) * k;
  }
} h[N];
int main() {
  int i, j, k, t, n, m;
  scanf("%d%d", &n, &m), b[0] = 2e9;
  for (i = 1, j = 0; i <= n; ++i)
    scanf("%d", a + i), j = max(j, a[i]), f[i + 1] = i * j;
  for (i = 2; i <= m; ++i) {
    swap(f, g), id = t = 0;
    for (j = i; j <= n; ++j) {
      h[j].d.resize(1), h[j].d[0] = j;
      while (t && a[st[t]] < a[j]) h[j].mg(h[st[t--]]);
      rt[j] = (lc[++id] = lc[rt[st[t]]], rc[id] = rc[rt[st[t]]],
               s[id] = s[rt[st[t]]], id),
      st[++t] = j, b[j] = h[j].qry(a[j]), upd(id, 1, n, j),
      f[j + 1] = qry(rt[j], 1, n, j);
    }
  }
  printf("%d", f[n + 1]);
  return 0;
}