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;
using pii = pair<int, int>;
const int NN = 20010, MM = 105;
int a[NN], dp[NN][MM], now;
pii operator-(const pii &a, const pii &b) {
  return make_pair(a.first - b.first, a.second - b.second);
}
int operator*(const pii &a, const pii &b) {
  return a.first * b.first + a.second * b.second;
}
int operator^(const pii &a, const pii &b) {
  return a.first * b.second - a.second * b.first;
}
pii conj(const pii &a) { return make_pair(-a.second, a.first); }
struct Hull {
  deque<pii> pts, vec;
  void addRight(const pii &a) {
    while (!vec.empty() && vec.back() * (a - pts.back()) < 0) {
      pts.pop_back();
      vec.pop_back();
    }
    if (!pts.empty()) vec.push_back(conj(a - pts.back()));
    pts.push_back(a);
  }
  void addLeft(const pii &a) {
    while (!vec.empty() && vec.front() * (a - pts.front()) < 0) {
      pts.pop_front();
      vec.pop_front();
    }
    if (!pts.empty()) vec.push_front(conj(pts.front() - a));
    pts.push_front(a);
  }
  int calc_min(const pii &a) {
    int it =
        lower_bound(vec.begin(), vec.end(), a,
                    [](const pii &a, const pii &b) { return (a ^ b) > 0; }) -
        vec.begin();
    return a * pts[it];
  }
};
struct State {
  int pos, root;
  Hull *hull;
};
const int M = 1 << 20;
int ls[M], rs[M];
pii p[M];
int new_node(const pii &a, int l = 0, int r = 0) {
  ++now;
  ls[now] = l;
  rs[now] = r;
  p[now] = a;
  return now;
}
const int inf = 0x3f3f3f3f;
int f(const pii &a, const int &first) { return a.first * first + a.second; }
int calc_min(int u, int L, int R, int first) {
  if (!u) return inf;
  if (L + 1 == R) return f(p[u], first);
  int md = L + R >> 1;
  if (first < md) return min(f(p[u], first), calc_min(ls[u], L, md, first));
  return min(f(p[u], first), calc_min(rs[u], md, R, first));
}
void merge_hull(Hull *&a, Hull *&c) {
  if (c->pts.size() >= a->pts.size()) {
    for (auto &d : a->pts) c->addRight(d);
  } else {
    for (auto it = c->pts.rbegin(); it != c->pts.rend(); it++) a->addLeft(*it);
    swap(a, c);
  }
}
int add(int u, int L, int R, pii a) {
  if (!u) return new_node(a);
  int mid = L + R >> 1;
  bool lf = f(a, L) < f(p[u], L);
  bool md = f(a, mid) < f(p[u], mid);
  int cur = new_node(p[u], ls[u], rs[u]);
  if (md) swap(p[cur], a);
  if (L + 1 == R) return cur;
  if (lf != md)
    ls[cur] = add(ls[u], L, mid, a);
  else
    rs[cur] = add(rs[u], mid, R, a);
  return cur;
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", a + i);
  int N = *max_element(a + 1, a + n + 1) + 3;
  memset(dp, 0x3f, sizeof dp);
  for (int i = 1, mx = 0; i <= n; i++) {
    mx = max(mx, a[i]);
    dp[i][1] = mx * i;
  }
  for (int i = 2; i <= k; i++) {
    now = 0;
    vector<State> st;
    vector<Hull *> tmp1;
    for (int j = i; j <= n; j++) {
      State cur;
      cur.pos = j;
      cur.hull = new Hull();
      tmp1.push_back(cur.hull);
      cur.hull->addRight({-j + 1, dp[j - 1][i - 1]});
      cur.root = 0;
      while (!st.empty() && a[st.back().pos] < a[j]) {
        merge_hull(st.back().hull, cur.hull);
        st.pop_back();
      }
      if (!st.empty()) cur.root = st.back().root;
      int val = cur.hull->calc_min({a[j], 1});
      cur.root = add(cur.root, 0, N, {a[j], val});
      st.push_back(cur);
      dp[j][i] = calc_min(st.back().root, 0, N, j);
    }
    for (auto first : tmp1) {
      first->pts.clear();
      first->vec.clear();
      delete first;
    }
  }
  cout << dp[n][k] << endl;
  return 0;
}