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;
int i, i0, n, k;
long long a[20005], mx[105][20005], pre[20005];
const double eps = 1e-12;
struct line {
  double k, b;
  int l, r;
  bool flag;
} tree[80005], L[20005];
double cal(line a, int pos) { return a.k * pos + a.b; }
int cross(line a, line b) { return floor((a.b - b.b) / (b.k - a.k)); }
void c_tree(int l, int r, int p, line k) {
  if (k.l <= l && r <= k.r) {
    if (!k.flag || !tree[p].flag) {
      tree[p] = k;
      if (l != r) tree[p * 2].flag = tree[p * 2 + 1].flag = 0;
    } else if (cal(k, l) > cal(tree[p], l) && cal(k, r) > cal(tree[p], r))
      tree[p] = k;
    else if (cal(k, l) > cal(tree[p], l) || cal(k, r) > cal(tree[p], r)) {
      int mid = (l + r) / 2;
      if (cross(k, tree[p]) <= mid) {
        if (k.k >= tree[p].k) swap(k, tree[p]);
        c_tree(l, mid, p * 2, k);
      } else {
        if (k.k <= tree[p].k) swap(k, tree[p]);
        c_tree(mid + 1, r, p * 2 + 1, k);
      }
    }
  } else {
    int mid = (l + r) / 2;
    if (k.l <= mid) c_tree(l, mid, p * 2, k);
    if (mid < k.r) c_tree(mid + 1, r, p * 2 + 1, k);
  }
}
double q_tree(int l, int r, int p, int x) {
  if (!tree[p].flag) return (double)INT_MIN * INT_MAX;
  if (l == r)
    return cal(tree[p], x);
  else {
    int mid = (l + r) / 2;
    double ans = cal(tree[p], x);
    if (x <= mid)
      return max(ans, q_tree(l, mid, p * 2, x));
    else
      return max(ans, q_tree(mid + 1, r, p * 2 + 1, x));
  }
}
void solve(int l, int r, int p) {
  long long mid = (l + r) / 2, x, i, i0;
  line t;
  for (i = mid, x = 0; i >= l; i--) x = max(x, a[i]), pre[i] = x;
  t.flag = 0, t.l = 1, t.r = 20000;
  c_tree(1, 20000, 1, t);
  for (i = mid + 1, i0 = mid, x = 0; i <= r; i++) {
    x = max(x, a[i]), pre[i] = x;
    while (i0 >= l && pre[i0] <= x) {
      t.flag = 1, t.l = 1, t.r = 20000, t.k = i0, t.b = -mx[p - 1][i0 - 1];
      c_tree(1, 20000, 1, t), i0--;
    }
    mx[p][i] = min(mx[p][i], (i + 1) * x - (long long)q_tree(1, 20000, 1, x));
  }
  t.flag = 0, t.l = 1, t.r = 20000;
  c_tree(1, 20000, 1, t);
  for (i = r, i0 = l; i > mid; i--) {
    while (i0 <= mid && pre[i0] >= pre[i]) {
      t.flag = 1, t.l = 1, t.r = 20000,
      t.b = -pre[i0] * (1 - i0) - mx[p - 1][i0 - 1], t.k = -pre[i0];
      c_tree(1, 20000, 1, t), i0++;
    }
    mx[p][i] = min(mx[p][i], -(long long)q_tree(1, 20000, 1, i));
  }
  if (l != r)
    solve(l, mid, p), solve(mid + 1, r, p);
  else
    mx[p][l] = min(mx[p][l], mx[p - 1][l - 1] + a[l]);
}
int main() {
  scanf("%d %d", &n, &k);
  long long x = 0;
  for (i = 1; i <= n; i++) {
    scanf("%lld", &a[i]);
    x = max(x, a[i]), mx[1][i] = x * i;
  }
  for (i = 2; i <= k; i++) {
    for (i0 = 1; i0 <= n; i0++) mx[i][i0] = mx[i - 1][i0];
    solve(1, n, i);
  }
  printf("%lld\n", mx[k][n]);
  return 0;
}