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>
const int N = 20005;
const int inf = 1e9;
int n, m, b[N], a[N], que[N], xi[N], yi[N], f[105][N], c[N];
void trans1(int l, int r, int le) {
  int mid = (l + r) / 2;
  int h = mid + 2, t = mid + 1, tot = 0;
  for (int i = mid - 1; i >= l; i--) {
    int x = b[i + 1], y = i * b[i + 1] - f[le - 1][i];
    if (!tot || x != xi[tot])
      xi[++tot] = x, yi[tot] = y;
    else
      yi[tot] = std::max(y, yi[tot]);
  }
  int p = tot;
  for (int i = r; i >= mid + 1; i--) {
    while (p >= 1 && xi[p] >= b[i]) {
      while (h < t &&
             (long long)(yi[p] - yi[que[h]]) * (xi[que[h]] - xi[que[h + 1]]) <
                 (long long)(yi[que[h]] - yi[que[h + 1]]) *
                     (xi[p] - xi[que[h]]))
        h++;
      que[--h] = p;
      p--;
    }
    if (p == tot) continue;
    int lef = h, rig = t - 1;
    while (lef <= rig) {
      int M = (lef + rig) / 2;
      if ((yi[que[M + 1]] - yi[que[M]]) >
          (long long)i * (xi[que[M + 1]] - xi[que[M]]))
        lef = M + 1;
      else
        rig = M - 1;
    }
    f[le][i] = std::min(f[le][i], xi[que[lef]] * i - yi[que[lef]]);
  }
}
void trans2(int l, int r, int le) {
  int mid = (l + r) / 2;
  int h = mid + 2, t = mid + 1, tot = 0;
  for (int i = l; i <= mid; i++) {
    int x = i, y = f[le - 1][i];
    xi[++tot] = x, yi[tot] = y;
  }
  int p = tot;
  for (int i = mid + 1; i <= r; i++) {
    while (p >= 1 && b[xi[p] + 1] <= b[i]) {
      while (h < t &&
             (long long)(yi[p] - yi[que[h]]) * (xi[que[h]] - xi[que[h + 1]]) >
                 (long long)(yi[que[h]] - yi[que[h + 1]]) *
                     (xi[p] - xi[que[h]]))
        h++;
      que[--h] = p;
      p--;
    }
    if (p == tot) continue;
    int lef = h, rig = t - 1;
    while (lef <= rig) {
      int M = (lef + rig) / 2;
      if (yi[que[M]] - xi[que[M]] * b[i] >=
          yi[que[M + 1]] - xi[que[M + 1]] * b[i])
        lef = M + 1;
      else
        rig = M - 1;
    }
    f[le][i] =
        std::min(f[le][i], yi[que[lef]] - xi[que[lef]] * b[i] + i * b[i]);
  }
  for (int i = mid + 1; i <= r; i++)
    f[le][i] = std::min(f[le][i], yi[que[t]] - xi[que[t]] * b[i] + i * b[i]);
}
void cdq(int l, int r, int le) {
  if (l == r) return;
  int mid = (l + r) / 2;
  cdq(l, mid, le);
  b[mid] = a[mid];
  for (int i = mid - 1; i >= l; i--) b[i] = std::max(b[i + 1], a[i]);
  b[mid + 1] = a[mid + 1];
  for (int i = mid + 2; i <= r; i++) b[i] = std::max(b[i - 1], a[i]);
  trans1(l, r, le);
  trans2(l, r, le);
  cdq(mid + 1, r, le);
}
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int mx = 0;
  for (int i = 1; i <= n; i++) mx = std::max(mx, a[i]), f[1][i] = mx * i;
  for (int j = 2; j <= m; j++) {
    for (int i = j - 1; i <= n; i++) f[j][i] = inf;
    cdq(j - 1, n, j);
  }
  printf("%d\n", f[m][n]);
  return 0;
}