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