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 = 20005, maxk = maxn * 20;
int n, k, now, lst, top, tot;
int a[maxn], b[maxn], f[2][maxn], stk[maxn], lc[maxk], rc[maxk], ans[maxk],
    rt[maxn];
deque<int> con[maxn];
inline int calc(int id, int X) { return a[id] * X + b[id]; }
inline int newnode(int x) {
  tot++, lc[tot] = lc[x], rc[tot] = rc[x], ans[tot] = ans[x];
  return tot;
}
void update(int l, int r, int now, int pos) {
  if (l == r) {
    if (calc(ans[now], l) > calc(pos, l)) ans[now] = pos;
    return;
  }
  int mid = (l + r) >> 1;
  if (calc(ans[now], mid) > calc(pos, mid)) swap(ans[now], pos);
  if (calc(ans[now], l) > calc(pos, l))
    lc[now] = newnode(lc[now]), update(l, mid, lc[now], pos);
  else
    rc[now] = newnode(rc[now]), update(mid + 1, r, rc[now], pos);
}
int query(int l, int r, int now, int X) {
  if (l == r) return calc(ans[now], X);
  int mid = (l + r) >> 1, res;
  if (X <= mid)
    res = query(l, mid, lc[now], X);
  else
    res = query(mid + 1, r, rc[now], X);
  return min(res, calc(ans[now], X));
}
inline int x(int p) { return p; }
inline int y(int p) { return f[lst][p]; }
inline double slope(int a, int b) {
  return x(a) == x(b) ? (y(a) > y(b) ? 1000000000 : -1000000000)
                      : 1.0 * (y(a) - y(b)) / (x(a) - x(b));
}
void merge_convex(int a, int b) {
  int flg = 0;
  if (con[a].size() > con[b].size()) {
    while (!con[b].empty()) {
      int p = con[b].back();
      while (con[a].size() > 1 &&
             slope(con[a][1], p) >= slope(con[a][1], con[a][0]))
        con[a].pop_front();
      con[a].push_front(p), con[b].pop_back();
    }
  } else {
    for (int i = 0; i < con[a].size(); i++) {
      int p = con[a][i];
      while (con[b].size() > 1 &&
             slope(p, con[b][con[b].size() - 2]) <=
                 slope(con[b].back(), con[b][con[b].size() - 2]))
        con[b].pop_back();
      con[b].push_back(p);
    }
    con[a].clear(), swap(con[a], con[b]);
  }
}
int find(int p, int X) {
  int L = 1, R = con[p].size() - 1;
  while (L <= R) {
    int mid = (L + R) >> 1;
    if (slope(con[p][mid], con[p][mid - 1]) < 1.0 * X)
      L = mid + 1;
    else
      R = mid - 1;
  }
  return f[lst][con[p][L - 1]] - (con[p][L - 1] - 1) * X;
}
int main() {
  scanf("%d%d", &n, &k);
  int tmp = 0;
  a[0] = 0, b[0] = 1000000000;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    tmp = max(tmp, a[i]), f[0][i + 1] = i * tmp;
  }
  now = 1, lst = 0;
  for (int i = 2; i <= k; i++) {
    top = tot = 0;
    for (int j = i; j <= n; j++) {
      con[j].clear(), con[j].push_back(j);
      while (top > 0 && a[j] >= a[stk[top]]) merge_convex(j, stk[top]), top--;
      rt[j] = newnode(rt[stk[top]]), stk[++top] = j;
      b[j] = find(j, a[j]), update(1, n, rt[j], j),
      f[now][j + 1] = query(1, n, rt[j], j);
    }
    lst = now, now ^= 1;
  }
  printf("%d\n", f[lst][n + 1]);
  return 0;
}