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;
const int N = 20100;
const int K = 110;
const int oo = 2e9;
const long long OO = 1e18;
int n, k, f[N][K], a[N], A[N], B[N], ck[N], cb[N], siz;
long long get_cross_point(long long k1, long long k2, long long b1,
                          long long b2) {
  long long B = b2 - b1;
  long long K = k1 - k2;
  if (K == 0) return (b1 < b2 ? -OO : OO);
  if ((B <= 0 && K < 0) || (B >= 0 && K > 0))
    return bool(B % K != 0) + B / K;
  else
    return B / K;
}
void calc(int kl, int l, int r) {
  if (l == r) {
    f[l][kl] = f[l - 1][kl - 1] + a[l];
    return;
  }
  int md = (l + r) >> 1;
  calc(kl, l, md);
  calc(kl, md + 1, r);
  for (int i = md + 1, mx = 0; i <= r; i++) {
    mx = max(mx, a[i]);
    A[i] = mx;
  }
  for (int i = md, mx = 0; i >= l; i--) {
    mx = max(mx, a[i]);
    B[i] = mx;
  }
  siz = 0;
  for (int i = md + 1, j = md, mem = 1; i <= r; i++) {
    while (j >= l && B[j] <= A[i]) {
      int nk = -(j - 1), nb = f[j - 1][kl - 1];
      while (siz > 1) {
        long long p1 = get_cross_point(ck[siz], nk, cb[siz], nb);
        long long p2 =
            get_cross_point(ck[siz - 1], ck[siz], cb[siz - 1], cb[siz]);
        if (p2 > p1) break;
        siz--;
      }
      siz++;
      ck[siz] = nk;
      cb[siz] = nb;
      j--;
    }
    if (siz == 0) continue;
    mem = min(mem, siz);
    while (mem < siz &&
           get_cross_point(ck[mem], ck[mem + 1], cb[mem], cb[mem + 1]) > A[i])
      mem++;
    while (mem > 1 &&
           get_cross_point(ck[mem], ck[mem - 1], cb[mem], cb[mem - 1]) <= A[i])
      mem--;
    f[i][kl] = min(f[i][kl], cb[mem] + (i + ck[mem]) * A[i]);
  }
  siz = 0;
  for (int i = r, j = l, mem = 1; i > md; i--) {
    while (j <= md && B[j] >= A[i]) {
      int nk = B[j], nb = f[j - 1][kl - 1] - (j - 1) * B[j];
      while (siz > 1) {
        long long p1 = get_cross_point(nk, ck[siz], nb, cb[siz]);
        long long p2 =
            get_cross_point(ck[siz - 1], ck[siz], cb[siz - 1], cb[siz]);
        if (p1 > p2) break;
        siz--;
      }
      if (ck[siz] == nk) {
        cb[siz] = min(nb, cb[siz]);
        j++;
        continue;
      }
      siz++;
      ck[siz] = nk;
      cb[siz] = nb;
      j++;
    }
    if (siz == 0) continue;
    mem = min(mem, siz);
    while (mem < siz &&
           get_cross_point(ck[mem], ck[mem + 1], cb[mem], cb[mem + 1]) <= i)
      mem++;
    while (mem > 1 &&
           get_cross_point(ck[mem], ck[mem - 1], cb[mem], cb[mem - 1]) > i)
      mem--;
    f[i][kl] = min(f[i][kl], ck[mem] * i + cb[mem]);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) cin >> a[i];
  f[0][1] = 0;
  for (int i = 1, mx = 0; i <= n; i++) {
    mx = max(mx, a[i]);
    f[i][1] = i * mx;
  }
  for (int kl = 2; kl <= k; kl++) {
    for (int i = kl; i <= n; i++) f[i][kl] = oo;
    calc(kl, kl, n);
  }
  cout << f[n][k];
  return 0;
}