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 = 20001;
const int maxk = 101;
const long long inf = 1e15;
struct vec {
  long long x, y;
  vec() {}
  vec(long long x, long long y) : x(x), y(y) {}
  vec operator-(const vec &v) const { return vec(x - v.x, y - v.y); }
  long long operator*(const vec &v) const { return x * v.y - y * v.x; }
  long long cal(long long a) { return x * a + y; }
};
struct node {
  node *ls, *rs;
  int l, r;
  vector<vec> stk;
  int pos;
};
struct lict {
  lict *ls, *rs;
  int l, r;
  vec f;
};
node pool_node[2 * maxn];
lict pool_lict[2 * maxn];
node *p_node = pool_node;
lict *p_lict = pool_lict;
node *create_node(int l, int r);
node *build_node(int l, int r);
lict *create_lict(int l, int r);
lict *build_lict(int l, int r);
void insert(node *p, int x, vec v);
long long query(node *p, int l, int r, vec v);
void insert(lict *p, int l, int r, vec f);
long long query(lict *p, int x);
int a[maxn];
int L[maxn], R[maxn];
int dp[maxn][maxk];
int f[maxn][maxk];
int n, k;
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  for (int i = 1; i <= n; i++) {
    L[i] = R[i] = i;
    while (L[i] > 1 && a[L[i] - 1] < a[i]) L[i]--;
    while (R[i] < n && a[R[i] + 1] <= a[i]) R[i]++;
  }
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= k; j++) {
      dp[i][j] = 1e9;
    }
  }
  dp[0][0] = 0;
  for (int j = 1; j <= k; j++) {
    p_node = pool_node;
    p_lict = pool_lict;
    node *rt_node = build_node(1, n);
    lict *rt_lict = build_lict(1, n);
    for (int i = j; i <= n; i++) {
      insert(rt_node, i, vec(i - 1, dp[i - 1][j - 1]));
      f[i][j] = query(rt_node, L[i], i, vec(1, a[i]));
      insert(rt_lict, i, R[i], vec(a[i], f[i][j]));
      dp[i][j] = query(rt_lict, i);
    }
  }
  printf("%d\n", dp[n][k]);
  return 0;
}
node *create_node(int l, int r) {
  p_node->l = l;
  p_node->r = r;
  p_node->ls = p_node->rs = NULL;
  p_node->pos = 0;
  p_node->stk.clear();
  return p_node++;
}
node *build_node(int l, int r) {
  node *p = create_node(l, r);
  if (l == r) return p;
  int mid = (l + r) / 2;
  p->ls = build_node(l, mid);
  p->rs = build_node(mid + 1, r);
  return p;
}
lict *create_lict(int l, int r) {
  p_lict->l = l;
  p_lict->r = r;
  p_lict->ls = p_lict->rs = NULL;
  p_lict->f = vec(0, inf);
  return p_lict++;
}
lict *build_lict(int l, int r) {
  lict *p = create_lict(l, r);
  if (l == r) return p;
  int mid = (l + r) / 2;
  p->ls = build_lict(l, mid);
  p->rs = build_lict(mid + 1, r);
  return p;
}
void insert(node *p, int x, vec v) {
  int sz;
  while (
      sz = p->stk.size(),
      sz >= 2 && (p->stk[sz - 1] - p->stk[sz - 2]) * (v - p->stk[sz - 1]) <= 0)
    p->stk.pop_back();
  p->stk.push_back(v);
  if (p->l == p->r) return;
  if (p->ls->r >= x)
    insert(p->ls, x, v);
  else
    insert(p->rs, x, v);
}
vec bound(vector<vec> &stk, vec v) {
  if (!stk.size()) return vec(0, inf);
  int l = 0;
  int r = stk.size() - 1;
  int mid = (l + r) / 2;
  while (r >= l) {
    if (mid != 0 && v * (stk[mid] - stk[mid - 1]) > 0)
      r = mid - 1;
    else if (mid + 1 < stk.size() && (stk[mid + 1] - stk[mid]) * v > 0)
      l = mid + 1;
    else
      return stk[mid];
    mid = (l + r) / 2;
  }
}
long long query(node *p, int l, int r, vec v) {
  if (p->l == l && p->r == r) return v * bound(p->stk, v);
  if (p->ls->r >= r)
    return query(p->ls, l, r, v);
  else if (p->rs->l <= l)
    return query(p->rs, l, r, v);
  else
    return min(query(p->ls, l, p->ls->r, v), query(p->rs, p->rs->l, r, v));
}
double inter(vec f1, vec f2) { return (double)(f2.y - f1.y) / (f1.x - f2.x); }
void insert(lict *p, int l, int r, vec f) {
  if (p->l == l && p->r == r) {
    if (p->f.cal(p->l) <= f.cal(p->l) && p->f.cal(p->r) <= f.cal(p->r)) return;
    if (f.cal(p->l) < p->f.cal(p->l) && f.cal(p->r) < p->f.cal(p->r)) {
      p->f = f;
      return;
    }
    if (f.cal(p->ls->r) < p->f.cal(p->ls->r)) {
      if (p->f.cal(p->l) < f.cal(p->l))
        insert(p->ls, p->l, p->ls->r, p->f);
      else
        insert(p->rs, p->rs->l, p->r, p->f);
      p->f = f;
    } else {
      if (f.cal(p->l) < p->f.cal(p->l))
        insert(p->ls, p->l, p->ls->r, f);
      else
        insert(p->rs, p->rs->l, p->r, f);
    }
    return;
  }
  if (p->ls->r >= r)
    insert(p->ls, l, r, f);
  else if (p->rs->l <= l)
    insert(p->rs, l, r, f);
  else
    insert(p->ls, l, p->ls->r, f), insert(p->rs, p->rs->l, r, f);
}
long long query(lict *p, int x) {
  long long ans = p->f.cal(x);
  if (p->l == p->r) return ans;
  if (p->ls->r >= x)
    ans = min(ans, query(p->ls, x));
  else
    ans = min(ans, query(p->rs, x));
  return ans;
}