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 maxn = 2e4 + 5;
struct tree {
  int c[2], sum;
} t[maxn * 20];
struct vec {
  int x, y;
  vec() {}
  vec(int x, int y) { this->x = x, this->y = y; }
  const vec operator-(const vec &b) const { return vec(x - b.x, y - b.y); }
  const long long operator*(const vec &b) const {
    return 1ll * x * b.y - 1ll * y * b.x;
  }
};
int k[maxn], b[maxn], rt[maxn], st[maxn], top, n, m, a[maxn], cnt, kc,
    f[2][maxn];
deque<vec> d[maxn];
int w(int p, int x) { return k[p] * x + b[p]; }
long long cal(vec a, int x) { return a.y - 1ll * (a.x - 1) * x; }
void add(int &id, int o, int l, int r, int v) {
  id = ++cnt, t[id] = t[o];
  int mid = l + r >> 1, &sm = t[id].sum;
  if ((w(v, l) <= w(sm, l) && w(v, r) <= w(sm, r)) || !sm)
    return sm = v, void();
  if (w(v, l) > w(sm, l) && w(v, r) > w(sm, r)) return;
  if (k[sm] < k[v])
    w(v, mid) < w(sm, mid) ? add(t[id].c[1], t[o].c[1], mid + 1, r, sm),
        sm = v, void() : add(t[id].c[0], t[o].c[0], l, mid, v);
  else
    w(v, mid) < w(sm, mid) ? add(t[id].c[0], t[o].c[0], l, mid, sm),
        sm = v, void() : add(t[id].c[1], t[o].c[1], mid + 1, r, v);
}
int ask(int id, int l, int r, int v) {
  if (!id) return 1e9;
  if (l == r) return w(t[id].sum, v);
  int mid = l + r >> 1;
  return min(
      v <= mid ? ask(t[id].c[0], l, mid, v) : ask(t[id].c[1], mid + 1, r, v),
      w(t[id].sum, v));
}
void merge(int x, int y) {
  if (d[x].size() >= d[y].size()) {
    for (register int i = d[y].size() - 1; i >= 0; i--) {
      while (d[x].size() > 1 && (d[x][1] - d[x][0]) * (d[x][0] - d[y][i]) >= 0)
        d[x].pop_front();
      d[x].push_front(d[y][i]);
    }
  } else {
    int tp = d[y].size() - 1;
    for (register int i = 0; i < d[x].size(); i++) {
      while (tp && (d[y][tp] - d[y][tp - 1]) * (d[x][i] - d[y][tp]) <= 0)
        d[y].pop_back(), tp--;
      d[y].push_back(d[x][i]), tp++;
    }
    swap(d[x], d[y]);
  }
}
int query(int i, int x) {
  int l = 1, r = d[i].size() - 1, ans = cal(d[i][0], x);
  while (l <= r) {
    int mid = l + r >> 1;
    if (cal(d[i][mid], x) <= cal(d[i][mid - 1], x))
      ans = cal(d[i][mid], x), l = mid + 1;
    else
      r = mid - 1;
  }
  return ans;
}
int main() {
  int mx = 0;
  scanf("%d%d", &n, &m);
  for (register int i = 1; i <= n; i++)
    scanf("%d", &a[i]), mx = max(mx, a[i]), f[1][i + 1] = i * mx;
  for (register int j = 2; j <= m; j++) {
    int now = j & 1, lst = now ^ 1;
    cnt = kc = top = 0;
    memset(t, 0, sizeof(t)), memset(rt, 0, sizeof(rt));
    for (register int i = j; i <= n; i++) {
      d[i].resize(1), d[i][0] = vec(i, f[lst][i]);
      while (top && a[st[top]] < a[i]) merge(i, st[top--]);
      k[++kc] = a[i], b[kc] = query(i, a[i]), add(rt[i], rt[st[top]], 1, n, kc);
      st[++top] = i, f[now][i + 1] = ask(rt[i], 1, n, i);
    }
  }
  printf("%d", f[m & 1][n + 1]);
  return 0;
}