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 long long N = 20010;
const long long K = 110;
const long long SZ = 500100;
const long long OO = 1e18;
long long f[N][K], a[N];
deque<pair<long long, long long> > dq[N];
long long n, k, id[N], loc[N], siz, lst, lef[SZ], rit[SZ], root[N];
long long func(pair<long long, long long> fn, long long vl) {
  return fn.first * vl + fn.second;
}
struct Li_Chao {
  pair<long long, long long> fn;
  Li_Chao() : fn(make_pair(0, OO)) {}
};
Li_Chao nodes[SZ];
void build(long long v, long long tl, long long tr) {
  nodes[v].fn = make_pair(0, OO);
  if (tl == tr) return;
  long long md = (tl + tr) >> 1;
  lef[v] = lst++;
  rit[v] = lst++;
  build(lef[v], tl, md);
  build(rit[v], md + 1, tr);
}
long long NEW(long long nm) {
  nodes[lst] = nodes[nm];
  lef[lst] = lef[nm];
  rit[lst] = rit[nm];
  lst++;
  return lst - 1;
}
void update(long long v, long long tl, long long tr,
            pair<long long, long long> nw) {
  long long md = (tl + tr) >> 1;
  bool lf = bool(func(nodes[v].fn, tl) > func(nw, tl));
  bool mid = bool(func(nodes[v].fn, md + 1) > func(nw, md + 1));
  if (mid) swap(nodes[v].fn, nw);
  if (tl == tr) return;
  if (lf != mid) {
    lef[v] = NEW(lef[v]);
    update(lef[v], tl, md, nw);
  } else {
    rit[v] = NEW(rit[v]);
    update(rit[v], md + 1, tr, nw);
  }
}
long long get(long long v, long long tl, long long tr, long long ps) {
  if (tl == tr) return func(nodes[v].fn, ps);
  long long md = (tl + tr) >> 1;
  if (ps <= md)
    return min(get(lef[v], tl, md, ps), func(nodes[v].fn, ps));
  else
    return min(get(rit[v], md + 1, tr, ps), func(nodes[v].fn, ps));
}
long long get_cross_point(pair<long long, long long> x,
                          pair<long long, long long> y) {
  long long B = (x.second - y.second);
  long long K = (y.first - x.first);
  long long vl = B / K;
  if ((B >= 0 && K > 0) || (B <= 0 && K < 0))
    return vl + bool(B % K > 0);
  else
    return vl;
}
long double get_cross_pold(pair<long long, long long> x,
                           pair<long long, long long> y) {
  long double B = (x.second - y.second);
  long double K = (y.first - x.first);
  return B / K;
}
void push(long long n1, long long n2, bool ed) {
  if (ed) {
    long long Siz = ((long long)dq[n2].size());
    for (long long it = 0; it < Siz; it++) {
      pair<long long, long long> nw = dq[n2][it];
      while (((long long)dq[n1].size()) > 1) {
        long long s1 = ((long long)dq[n1].size());
        long double p1 = get_cross_pold(dq[n1][s1 - 2], nw);
        long double p2 = get_cross_pold(dq[n1][s1 - 2], dq[n1].back());
        if (p1 >= p2) break;
        dq[n1].pop_back();
      }
      dq[n1].push_back(nw);
    }
  } else {
    for (long long it = ((long long)dq[n2].size()) - 1; it >= 0; it--) {
      pair<long long, long long> nw = dq[n2][it];
      while (((long long)dq[n1].size()) > 1) {
        long double p1 = get_cross_pold(dq[n1][1], dq[n1][0]);
        long double p2 = get_cross_pold(dq[n1][1], nw);
        if (p1 >= p2) break;
        dq[n1].pop_front();
      }
      dq[n1].push_front(nw);
    }
  }
}
long long get(long long nm, long long ps) {
  long long l = 0, r = ((long long)dq[nm].size()) - 1;
  while (l < r) {
    long long md = (l + r + 1) >> 1;
    long long pot = get_cross_point(dq[nm][md], dq[nm][md - 1]);
    if (pot > ps)
      r = md - 1;
    else
      l = md;
  }
  return func(dq[nm][l], ps);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (long long i = 1; i <= n; i++) cin >> a[i];
  for (long long i = 1, mx = 0; i <= n; i++) {
    mx = max(mx, (long long)a[i]);
    f[i][1] = mx * i;
  }
  for (long long kl = 2; kl <= k; kl++) {
    siz = root[0] = 0;
    lst = 1;
    build(0, 1, N);
    for (long long i = kl; i <= n; i++) {
      id[i] = i;
      dq[i].clear();
      dq[i].push_back(make_pair(-(i - 1), f[i - 1][kl - 1]));
      while (siz > 0 && a[loc[siz]] <= a[i]) {
        long long ps = loc[siz];
        if (((long long)dq[id[ps]].size()) > ((long long)dq[id[i]].size())) {
          push(id[ps], id[i], 1);
          id[i] = id[ps];
        } else
          push(id[i], id[ps], 0);
        siz--;
      }
      siz++;
      loc[siz] = i;
      root[siz] = NEW(root[siz - 1]);
      long long mem = get(id[i], a[i]);
      update(root[siz], 1, N, make_pair(a[i], mem));
      f[i][kl] = get(root[siz], 1, N, i);
    }
  }
  cout << f[n][k];
  return 0;
}