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;
template <class T>
void read(T &x) {
  int f = 0;
  x = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar()) f |= (ch == '-');
  for (; isdigit(ch); ch = getchar()) x = x * 10 + ch - '0';
  if (f) x = -x;
}
const int N = 20005, inf = 1e9;
struct pt {
  int x, y;
  friend long long cro(pt p, pt a, pt b) {
    return (long long)(a.x - p.x) * (b.y - p.y) -
           (long long)(a.y - p.y) * (b.x - p.x);
  }
};
vector<pt> T[N << 2];
int p[N << 2];
int a[N], rk[N], mx[N][18], lg[N];
int lc[N], rc[N], L[N], R[N], t[N];
int f[N], g[N], n, K, rt;
int cmp1(int x, int y) { return a[x] > a[y]; }
int Mx(int x, int y) { return cmp1(x, y) ? x : y; }
int getmx(int l, int r) {
  int t = lg[r - l + 1];
  return Mx(mx[l][t], mx[r - (1 << t) + 1][t]);
}
int doit(int l, int r) {
  int o = getmx(l, r);
  L[o] = l, R[o] = r;
  if (l < o) lc[o] = doit(l, o - 1);
  if (o < r) rc[o] = doit(o + 1, r);
  return o;
}
void init() {
  for (int o = (1); o <= (n << 2); o++) {
    T[o].clear();
    p[o] = 0;
  }
}
void build(int o, int l, int r) {
  vector<pt> nw;
  int sz = 0;
  for (int k = 0; k < (((int)T[o].size())); k++) {
    while (sz >= 2 && cro(nw[sz - 2], nw[sz - 1], T[o][k]) <= 0) {
      nw.pop_back(), sz--;
    }
    nw.push_back(T[o][k]), sz++;
  }
  T[o] = nw;
  p[o] = ((int)T[o].size()) - 1;
  if (l == r) return;
  build((o << 1), l, ((l + r) >> 1));
  build((o << 1 | 1), ((l + r) >> 1) + 1, r);
}
void ins(int o, int l, int r, int x, int y, pt z, int ty) {
  if (ty == 0) T[o].push_back(z);
  if (l == x && y == r) {
    if (ty == 1) T[o].push_back(z);
    return;
  }
  if (x <= ((l + r) >> 1))
    ins((o << 1), l, ((l + r) >> 1), x, min(y, ((l + r) >> 1)), z, ty);
  if (((l + r) >> 1) < y)
    ins((o << 1 | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, x), y, z,
        ty);
}
int result;
int F(pt &x, int y) { return x.x * y + x.y; }
void ask(int o, int v) {
  while (p[o] >= 1 && F(T[o][p[o] - 1], v) < F(T[o][p[o]], v)) p[o]--;
  if (p[o] >= 0) result = min(result, F(T[o][p[o]], v));
}
void qry(int o, int l, int r, int x, int y, int z, int ty) {
  if (ty == 0) ask(o, z);
  if (l == x && y == r) {
    if (ty == 1) ask(o, z);
    return;
  }
  if (x <= ((l + r) >> 1))
    qry((o << 1), l, ((l + r) >> 1), x, min(y, ((l + r) >> 1)), z, ty);
  if (((l + r) >> 1) < y)
    qry((o << 1 | 1), ((l + r) >> 1) + 1, r, max(((l + r) >> 1) + 1, x), y, z,
        ty);
}
int main() {
  read(n), read(K);
  lg[0] = -1;
  for (int i = (1); i <= (n); i++) {
    read(a[i]);
    rk[i] = i;
    mx[i][0] = i;
    lg[i] = lg[i >> 1] + 1;
  }
  sort(rk + 1, rk + n + 1, cmp1);
  for (int i = (n); i >= (1); i--) {
    for (int j = 1; i + (1 << j) - 1 <= n; j++) {
      mx[i][j] = Mx(mx[i][j - 1], mx[i + (1 << (j - 1))][j - 1]);
    }
  }
  rt = doit(1, n);
  memset(f, 0x3f, sizeof f);
  f[0] = 0;
  while (K--) {
    memset(g, 0x3f, sizeof g);
    init();
    for (int i = (n); i >= (0); i--) {
      ins(1, 0, n, i, i, (pt){n - i, f[i]}, 0);
    }
    build(1, 0, n);
    for (int i = (1); i <= (n); i++) {
      int k = rk[n + 1 - i];
      result = inf, qry(1, 0, n, L[k] - 1, k - 1, a[k], 1), t[k] = result;
      t[k] -= (n - k) * a[k];
    }
    init();
    for (int i = (1); i <= (n); i++) {
      int k = rk[n + 1 - i];
      ins(1, 0, n, k, R[k], (pt){a[k], t[k] - a[k] * k}, 1);
    }
    build(1, 0, n);
    for (int i = (1); i <= (n); i++) {
      result = inf, qry(1, 0, n, i, i, i, 0), g[i] = result;
    }
    memcpy(f, g, sizeof f);
  }
  printf("%d\n", f[n]);
  return 0;
}