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];
struct line {
  long long k, b;
  int l, r;
  bool flag;
} tree[80005];
long long cal(line a, int pos) { return a.k * pos + a.b; }
long long cross(line a, line b) { return (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))) {
      if (cal(k, l) <= cal(tree[p], l) && cal(k, r) <= cal(tree[p], r))
        tree[p] = k;
    } else {
      int mid = (l + r) / 2;
      if (cross(k, tree[p]) <= mid) {
        if (cal(k, r) < cal(tree[p], r)) swap(k, tree[p]);
        c_tree(l, mid, p * 2, k);
      } else {
        if (cal(k, l) < cal(tree[p], l)) 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);
  }
}
long long q_tree(int l, int r, int p, int x) {
  if (!tree[p].flag) return (long long)INT_MAX * INT_MAX;
  if (l == r)
    return cal(tree[p], x);
  else {
    int mid = (l + r) / 2;
    long long ans = cal(tree[p], x);
    if (x <= mid)
      return min(ans, q_tree(l, mid, p * 2, x));
    else
      return min(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);
  t.flag = 1, t.l = 1, t.r = 20000, t.k = -(mid + 1), t.b = mx[p - 1][mid],
  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 + 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.k = pre[i0],
      t.b = mx[p - 1][i0 - 1] - pre[i0] * (i0 - 1), c_tree(1, 20000, 1, t),
      i0++;
    mx[p][i] = min(mx[p][i], q_tree(1, 20000, 1, i));
  }
  if (l != r) solve(l, mid, p), solve(mid + 1, r, p);
}
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;
}