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) {
  static int c, neg;
  x = neg = 0;
  c = getchar();
  while (!isdigit(c)) {
    if (c == '-') neg = 1;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - 48;
    c = getchar();
  }
  if (neg) x = -x;
}
template <class T>
void print(T x, char c = '\n') {
  static int st[233], top;
  if (x < 0) putchar('-'), x = -x;
  do {
    st[++top] = x % 10;
    x /= 10;
  } while (x);
  while (top) putchar(st[top--] + 48);
  putchar(c);
}
template <class T>
void cmax(T& x, const T& y) {
  x = (x > y) ? x : y;
}
template <class T>
void cmin(T& x, const T& y) {
  x = (x < y) ? x : y;
}
int n, k;
const int N = 2e4 + 5;
int a[N];
int f[N][16];
int cmp(int x, int y) { return a[x] > a[y] ? x : y; }
int lg[N];
void init() {
  for (int i = 2; i <= N - 1; i++) {
    lg[i] = lg[i >> 1] + 1;
  }
  for (int i = 1; i <= n; i++) {
    f[i][0] = i;
  }
  for (int j = 1; j <= 15; j++) {
    for (int i = 1; i <= n - (1 << j) + 1; i++) {
      int x = f[i][j - 1];
      int y = f[i + (1 << j - 1)][j - 1];
      f[i][j] = cmp(x, y);
    }
  }
}
int get(int l, int r) {
  int t = lg[r - l + 1];
  int x = f[l][t];
  int y = f[r - (1 << t) + 1][t];
  return cmp(x, y);
}
struct line {
  int x, y;
  line() {
    x = 0;
    y = 0;
  }
  line(int _, int __) {
    x = _;
    y = __;
  }
  int val(int _) { return x * _ + y; }
} c[N << 2];
struct point {
  int x, y;
  point(int _, int __) {
    x = _;
    y = __;
  }
};
deque<point> tmp[N];
bool vis[N << 2];
void build(int l, int r, int p) {
  vis[p] = false;
  c[p] = line(0, 0);
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
}
void ins(int l, int r, int p, line v) {
  if (!vis[p]) {
    vis[p] = true;
    c[p] = v;
    return;
  }
  int mid = l + r >> 1;
  int mid1 = c[p].val(mid);
  int mid2 = v.val(mid);
  if (mid1 > mid2) swap(c[p], v);
  int l1 = c[p].val(l);
  int l2 = v.val(l);
  int r1 = c[p].val(r);
  int r2 = v.val(r);
  if (l1 <= l2 && r1 <= r2) {
    return;
  }
  if (l1 > l2) {
    ins(l, mid, p << 1, v);
  } else {
    ins(mid + 1, r, p << 1 | 1, v);
  }
}
void ins(int ql, int qr, int l, int r, int p, line v) {
  if (ql <= l && r <= qr) {
    ins(l, r, p, v);
    return;
  }
  int mid = l + r >> 1;
  if (ql <= mid) ins(ql, qr, l, mid, p << 1, v);
  if (qr > mid) ins(ql, qr, mid + 1, r, p << 1 | 1, v);
}
int query(int l, int r, int p, int x) {
  int res = vis[p] ? c[p].val(x) : 1e9;
  if (l == r) return res;
  int mid = l + r >> 1;
  if (x <= mid) {
    cmin(res, query(l, mid, p << 1, x));
  } else {
    cmin(res, query(mid + 1, r, p << 1 | 1, x));
  }
  return res;
}
double K(point a, point b) {
  double res = 1. * (b.y - a.y) / (b.x - a.x);
  return res;
}
line calc(int x, int y) {
  if (!tmp[x].size()) {
    return line(0, 1e9);
  }
  while (tmp[x].size() > 1 && K(tmp[x][0], tmp[x][1]) <= y) {
    tmp[x].pop_front();
  }
  return line(y, tmp[x][0].y - tmp[x][0].x * y);
}
void pushback(int x, point y) {
  while (tmp[x].size() > 1) {
    int now = (int)tmp[x].size();
    now -= 2;
    point a = tmp[x][now];
    ++now;
    point b = tmp[x][now];
    if (K(a, y) <= K(a, b)) {
      tmp[x].pop_back();
    } else {
      break;
    }
  }
  tmp[x].push_back(y);
}
void pushfront(int x, point y) {
  while (tmp[x].size() > 1) {
    int now = 0;
    point a = tmp[x][now];
    ++now;
    point b = tmp[x][now];
    if (K(y, b) <= K(y, a)) {
      tmp[x].pop_front();
    } else {
      break;
    }
  }
  tmp[x].push_front(y);
}
int ff[101][N];
int t = 0;
int st[N], top = 0;
int solve(int l, int r) {
  if (l == r) {
    int u = st[top--];
    tmp[u].push_back(point(l, ff[t - 1][l]));
    return u;
  }
  int pos, L, R;
  pos = get(l + 1, r);
  L = solve(l, pos - 1);
  line s = calc(L, a[pos]);
  ins(pos, r, 1, n, 1, s);
  ff[t][pos] = query(1, n, 1, pos);
  R = solve(pos, r);
  if (tmp[L].size() < tmp[R].size()) {
    while (tmp[L].size()) {
      pushfront(R, tmp[L].back());
      tmp[L].pop_back();
    }
    st[++top] = L;
    return R;
  } else {
    while (tmp[R].size()) {
      pushback(L, tmp[R].front());
      tmp[R].pop_front();
    }
    st[++top] = R;
    return L;
  }
}
int main() {
  read(n);
  read(k);
  for (int i = 1; i <= n; i++) {
    read(a[i]);
  }
  init();
  for (int i = 1; i <= n; i++) {
    st[++top] = i;
  }
  for (int i = 1; i <= n; i++) {
    ff[1][i] = i * a[get(1, i)];
  }
  ++t;
  for (int i = 2; i <= k; i++) {
    ++t;
    build(1, n, 1);
    solve(i - 1, n);
  }
  print(ff[k][n]);
  return 0;
}