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>
long long min(long long a, long long b) { return a < b ? a : b; }
int max(int a, int b) { return a > b ? a : b; }
long long dot2(int x1, int y1, int x2, int y2) {
  return (long long)x1 * x2 + (long long)y1 * y2;
}
long long cross2(int x1, int y1, int x2, int y2) {
  return (long long)x1 * y2 - (long long)x2 * y1;
}
int xx[20000 + 1], yy[20000 + 1];
long long cross(int i, int j, int k) {
  return cross2(xx[j] - xx[i], yy[j] - yy[i], xx[k] - xx[i], yy[k] - yy[i]);
}
int aa[20000 + 1], dp[20000 + 1], dq[20000 + 1];
void solve(int l, int r) {
  static int qu[20000 + 1], qq[20000 + 1], pp[20000 + 1];
  int m, h, i, j, q, p, cnt;
  if (r - l == 1) return;
  m = (l + r) / 2;
  solve(l, m);
  solve(m, r);
  q = 0;
  for (i = m - 1; i >= l; i--) qq[i] = q = max(q, aa[i]);
  p = 0;
  for (i = m; i < r; i++) pp[i] = p, p = max(p, aa[i]);
  cnt = 0;
  for (j = m, i = m - 1, h = 0; j < r; j++) {
    while (i >= l && qq[i] <= pp[j]) {
      xx[i] = i, yy[i] = dp[i];
      while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) >= 0) cnt--;
      qu[cnt++] = i;
      if (h >= cnt - 2) h = cnt - 1;
      i--;
    }
    while (h > 0 && dot2(xx[qu[h]], yy[qu[h]], pp[j], -1) <
                        dot2(xx[qu[h - 1]], yy[qu[h - 1]], pp[j], -1))
      h--;
    if (cnt)
      dq[j] = min(dq[j], pp[j] * j - dot2(xx[qu[h]], yy[qu[h]], pp[j], -1));
  }
  cnt = 0;
  for (j = r - 1, i = l, h = 0; j >= m; j--) {
    while (i < m && qq[i] > pp[j]) {
      xx[i] = qq[i], yy[i] = dp[i] - qq[i] * i;
      if (cnt && xx[qu[cnt - 1]] == xx[i]) {
        if (yy[qu[cnt - 1]] > yy[i])
          cnt--;
        else {
          i++;
          continue;
        }
      }
      while (cnt >= 2 && cross(qu[cnt - 2], qu[cnt - 1], i) >= 0) cnt--;
      qu[cnt++] = i;
      if (h >= cnt - 2) h = cnt - 1;
      i++;
    }
    while (h > 0 && dot2(xx[qu[h]], yy[qu[h]], -j, -1) <
                        dot2(xx[qu[h - 1]], yy[qu[h - 1]], -j, -1))
      h--;
    if (cnt) dq[j] = min(dq[j], -dot2(xx[qu[h]], yy[qu[h]], -j, -1));
  }
}
int main() {
  int n, k, i;
  scanf("%d%d", &n, &k);
  for (i = 0; i < n; i++) scanf("%d", &aa[i]);
  memset(dp, 0x3f, (n + 1) * sizeof *dp), dp[0] = 0;
  while (k--) {
    memset(dq, 0x3f, (n + 1) * sizeof *dq);
    solve(0, n + 1);
    memcpy(dp, dq, (n + 1) * sizeof *dp);
  }
  printf("%d\n", dp[n]);
  return 0;
}