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>
#pragma GCC optimize("O3")
using namespace std;
int n, k;
const int maxN = 2 * (int)1e4 + 100;
vector<pair<long long, long long> > cht[4 * maxN];
struct pt {
  long long x, y;
  pt(long long _x, long long _y) {
    x = _x;
    y = _y;
  }
  pt() {}
};
vector<pt> all[4 * maxN];
bool del(const pt& x, const pt& y, const pt& z) {
  return (y.y - x.y) * (x.x - z.x) <= (z.y - x.y) * (x.x - y.x);
}
void add(long long x, long long y, vector<pt>& vec) {
  pt nw(x, y);
  while (vec.size() >= 2 && del(vec[vec.size() - 1], vec[vec.size() - 2], nw)) {
    vec.pop_back();
  }
  vec.push_back(nw);
}
long long get(const pt& a, long long y) { return (a.x * y + a.y); }
const long long INF = 2 * (long long)1e18;
long long get(long long x, vector<pt>& vec) {
  if (vec.empty()) return -INF;
  int l = 0;
  int r = vec.size() - 1;
  while (r - l > 1) {
    int m = (l + r) / 2;
    if (get(vec[m], x) > get(vec[m + 1], x)) {
      r = m;
    } else
      l = m;
  }
  return max(get(vec[r], x), get(vec[l], x));
}
void add(int v, int tl, int tr, int l, int r, pair<long long, long long>& who) {
  if (tl == l && tr == r) {
    cht[v].push_back(who);
    return;
  }
  int tm = (tl + tr) / 2;
  if (r <= tm) {
    add(v + v, tl, tm, l, r, who);
  } else if (l > tm) {
    add(v + v + 1, tm + 1, tr, l, r, who);
  } else {
    add(v + v, tl, tm, l, tm, who);
    add(v + v + 1, tm + 1, tr, tm + 1, r, who);
  }
}
void ch() {
  for (int i = 1; i <= 4 * n; i++) {
    cht[i].clear();
    all[i].clear();
  }
}
void build(int v, int tl, int tr) {
  sort(cht[v].begin(), cht[v].end());
  reverse(cht[v].begin(), cht[v].end());
  for (auto t : cht[v]) {
    add(-t.first, -t.second, all[v]);
  }
  if (tl != tr) {
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
  }
}
long long get(int v, int tl, int tr, int pos, long long val) {
  long long f1 = -get(val, all[v]);
  if (tl != tr) {
    int tm = (tl + tr) / 2;
    if (pos <= tm)
      f1 = min(f1, get(v + v, tl, tm, pos, val));
    else
      f1 = min(f1, get(v + v + 1, tm + 1, tr, pos, val));
  }
  return f1;
}
long long dp[maxN];
int a[maxN];
int nxt[maxN];
long long coefs[maxN];
vector<pt> lines[4 * maxN];
pair<long long, long long> ss[4 * maxN];
void build2(int v, int tl, int tr) {
  vector<pair<long long, long long> > all;
  for (int i = tl; i <= tr; i++) {
    all.push_back(ss[i]);
  }
  sort(all.begin(), all.end());
  reverse(all.begin(), all.end());
  for (auto it : all) {
    add(-it.first, -it.second, lines[v]);
  }
  int tm = (tl + tr) / 2;
  if (tl != tr) {
    build2(v + v, tl, tm);
    build2(v + v + 1, tm + 1, tr);
  }
}
long long get_val(int v, int tl, int tr, int l, int r, long long val) {
  if (tl == l && tr == r) {
    return -get(val, lines[v]);
  }
  int tm = (tl + tr) / 2;
  if (r <= tm)
    return get_val(v + v, tl, tm, l, r, val);
  else if (l > tm)
    return get_val(v + v + 1, tm + 1, tr, l, r, val);
  else {
    return min(get_val(v + v, tl, tm, l, tm, val),
               get_val(v + v + 1, tm + 1, tr, tm + 1, r, val));
  }
}
int en[maxN];
void solve() {
  vector<pair<int, int> > st;
  st.push_back(make_pair(1e9, 0));
  for (int i = 1; i <= 4 * n; i++) lines[i].clear();
  for (int i = 1; i <= n; i++) {
    ss[i] = make_pair(-(i - 1), dp[i - 1]);
  }
  build2(1, 1, n);
  for (int i = 1; i <= n; i++) {
    while (make_pair(a[i], i) > st.back()) {
      st.pop_back();
    }
    nxt[i] = st.back().second;
    st.push_back(make_pair(a[i], i));
  }
  for (int i = 1; i <= n; i++) {
    coefs[i] = get_val(1, 1, n, nxt[i] + 1, i, a[i]);
  }
  ch();
  st.clear();
  st.push_back(make_pair(1e9, 0));
  for (int i = 1; i <= n; i++) {
    while (make_pair(a[i], i) > st.back()) {
      en[st.back().second] = i - 1;
      st.pop_back();
    }
    st.push_back(make_pair(a[i], i));
  }
  while (!st.empty()) {
    en[st.back().second] = n;
    st.pop_back();
  }
  for (int i = 1; i <= n; i++) {
    pair<long long, long long> tt = make_pair(a[i], coefs[i]);
    add(1, 1, n, i, en[i], tt);
  }
  build(1, 1, n);
  dp[0] = 1e9;
  for (int i = 1; i <= n; i++) {
    dp[i] = get(1, 1, n, i, i);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  dp[0] = 0;
  for (int i = 1; i <= n; i++) {
    dp[i] = (long long)1e9;
  }
  for (int i = 0; i < k; i++) {
    solve();
  }
  cout << dp[n];
  return 0;
}