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 inf = 1e9;
const long long INF = 1e18;
const double eps = 1e-10;
const double pi = acos(-1);
mt19937 mrand(chrono::high_resolution_clock::now().time_since_epoch().count());
template <class T>
inline void upmin(T &x, T y) {
  x = x > y ? y : x;
}
template <class T>
inline void upmax(T &x, T y) {
  x = x < y ? y : x;
}
const int maxn = 2e4 + 233;
template <class T>
struct Intervel {
  T k, b;
  int flag;
  Intervel(T kk = 0, T bb = 0, T ff = 0) {
    k = kk;
    b = bb;
    flag = ff;
  }
  T cal(T x) { return k * x + b; }
};
template <class T>
struct LiChao_Segment {
  Intervel<T> seg_mn[maxn << 2];
  T mn[maxn << 2];
  void up(int o) { mn[o] = min(mn[o], min(mn[o << 1], mn[o << 1 | 1])); }
  void build(int o, int l, int r) {
    mn[o] = INF;
    seg_mn[o] = Intervel<long long>();
    if (l == r) return;
    int mid = l + r >> 1;
    build(o << 1, l, mid);
    build(o << 1 | 1, mid + 1, r);
    up(o);
  }
  void clear(int o, int l, int r) {
    mn[o] = INF;
    seg_mn[o] = Intervel<long long>();
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    if (seg_mn[o << 1].flag) clear(o << 1, l, mid);
    if (seg_mn[o << 1 | 1].flag) clear(o << 1 | 1, mid + 1, r);
  }
  void updmin(int o, int tl, int tr, int l, int r, Intervel<T> v) {
    if (l > tr || tl > r) return;
    int mid = tl + tr >> 1;
    if (l <= tl && tr <= r) {
      if (!seg_mn[o].flag) {
        seg_mn[o] = v;
        mn[o] = min(mn[o], min(seg_mn[o].cal(tl), seg_mn[o].cal(tr)));
        return;
      }
      if (v.cal(tl) <= seg_mn[o].cal(tl) && v.cal(tr) <= seg_mn[o].cal(tr)) {
        seg_mn[o] = v;
        mn[o] = min(mn[o], min(seg_mn[o].cal(tl), seg_mn[o].cal(tr)));
        return;
      }
      if (v.cal(tl) <= seg_mn[o].cal(tl) || v.cal(tr) <= seg_mn[o].cal(tr)) {
        if (v.cal(mid) < seg_mn[o].cal(mid)) swap(seg_mn[o], v);
        mn[o] = min(mn[o], min(seg_mn[o].cal(tl), seg_mn[o].cal(tr)));
        if (v.cal(tl) < seg_mn[o].cal(tl))
          updmin(o << 1, tl, mid, l, r, v);
        else
          updmin(o << 1 | 1, mid + 1, tr, l, r, v);
        up(o);
      }
      return;
    }
    updmin(o << 1, tl, mid, l, r, v);
    updmin(o << 1 | 1, mid + 1, tr, l, r, v);
    up(o);
  }
  T qmin(int o, int tl, int tr, int l, int r) {
    if (l > tr || tl > r) return 1e18;
    if (l <= tl && tr <= r) return mn[o];
    int mid = tl + tr >> 1;
    T res = 1e18;
    if (seg_mn[o].flag)
      res = min(res, min(seg_mn[o].cal(max(tl, l)), seg_mn[o].cal(min(tr, r))));
    res = min(res, qmin(o << 1, tl, mid, l, r));
    res = min(res, qmin(o << 1 | 1, mid + 1, tr, l, r));
    return res;
  }
};
int n;
long long dp[maxn][110];
int a[maxn];
LiChao_Segment<long long> tr;
int pre[maxn], suf[maxn];
int q[maxn], head, tail;
void solve(int l, int r, int k) {
  if (l == r) {
    return;
  }
  int mid = l + r >> 1;
  solve(l, mid, k);
  int mx = 0;
  for (int i = mid; i >= l; i--) {
    mx = max(mx, a[i]);
    suf[i] = mx;
  }
  mx = 0;
  for (int i = mid + 1; i <= r; i++) {
    mx = max(mx, a[i]);
    pre[i] = mx;
  }
  int pl = l;
  suf[mid + 1] = 0;
  for (int i = r; i > mid; i--) {
    while (pl <= mid && suf[pl + 1] >= pre[i]) {
      tr.updmin(1, 0, 2e4, 0, 2e4,
                Intervel<long long>(suf[pl + 1],
                                    dp[pl][k - 1] - 1ll * pl * suf[pl + 1], 1));
      pl++;
    }
    dp[i][k] = min(dp[i][k], tr.qmin(1, 0, 2e4, i, i));
  }
  tr.clear(1, 0, 2e4);
  head = 1, tail = 0;
  auto up = [&](int j, int i) { return dp[i][k - 1] - dp[j][k - 1]; };
  auto down = [&](int j, int i) { return (mid - i) - (mid - j); };
  pl = mid;
  head = tail = 1;
  q[head] = mid;
  for (int i = mid + 1; i <= r; i++) {
    while (pl > l && suf[pl] <= pre[i]) {
      pl--;
      while (head < tail && up(q[tail - 1], q[tail]) * down(q[tail], pl) >=
                                down(q[tail - 1], q[tail]) * up(q[tail], pl))
        tail--;
      q[++tail] = pl;
    }
    if (head > tail) continue;
    int lb = head + 1, ub = tail, ans = head;
    while (ub >= lb) {
      int m = ub + lb >> 1;
      if (up(q[m - 1], q[m]) <= -down(q[m - 1], q[m]) * pre[i])
        lb = m + 1, ans = m;
      else
        ub = m - 1;
    }
    dp[i][k] = min(dp[i][k], dp[q[ans]][k - 1] + 1ll * (i - q[ans]) * pre[i]);
  }
  solve(mid + 1, r, k);
}
int k;
int main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  cout << fixed << setprecision(10);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= k; ++j) {
      dp[i][j] = inf;
    }
  }
  dp[0][0] = 0;
  for (int i = 1; i <= k; ++i) {
    tr.build(1, 0, 2e4);
    solve(0, n, i);
  }
  cout << dp[n][k] << '\n';
  return 0;
}