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;
template <class T1, class T2>
inline void chkmin(T1 &x, const T2 &y) {
  if (x > y) x = y;
}
template <class T1, class T2>
inline void chkmax(T1 &x, const T2 &y) {
  if (x < y) x = y;
}
const int MAXN = 20009;
struct Line {
  long long k, b;
  Line() {}
  Line(long long _k, long long _b) {
    k = _k;
    b = _b;
  }
  long long value(long long x) { return 1LL * k * x + b; }
};
bool operator<(const Line &b, const Line &a) {
  return b.k < a.k || (b.k == a.k && b.b < a.b);
}
bool better(Line a, Line b, Line c) {
  return 1LL * (c.b - a.b) * (a.k - b.k) <= 1LL * (b.b - a.b) * (a.k - c.k);
}
struct ConvexHull {
  vector<Line> st;
  void addLine(Line x) {
    while ((int)(st).size() >= 2 &&
           better(st[(int)(st).size() - 2], st.back(), x)) {
      st.pop_back();
    }
    st.push_back(x);
  }
  long long getmax(int x) {
    if (st.empty()) {
      return -1e12;
    }
    int l = 0;
    int r = (int)(st).size() - 1;
    while (l + 3 < r) {
      int mid = (l + r) >> 1;
      if ((st[mid + 1].b - st[mid].b) >=
          1LL * x * (st[mid].k - st[mid + 1].k)) {
        l = mid;
      } else {
        r = mid;
      }
    }
    long long kek = -1e12;
    for (int i = l; i <= r; i++) {
      chkmax(kek, st[i].value(x));
    }
    return kek;
  }
};
int n, k;
int a[MAXN];
ConvexHull st[MAXN * 4];
ConvexHull st1[MAXN * 4];
int ss = 1;
long long dp[MAXN][102];
int ls[MAXN], rs[MAXN];
void add(int i, Line l) {
  while (i) {
    st[i].addLine(l);
    i >>= 1;
  }
}
long long getmax(int v, int vl, int vr, int l, int r, int x) {
  if (vl > r || vr < l) {
    return -1e12;
  }
  if (l <= vl && vr <= r) {
    return st[v].getmax(x);
  }
  return max(getmax(v * 2, vl, (vl + vr) / 2, l, r, x),
             getmax(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x));
}
void add(int v, int vl, int vr, int l, int r, Line x) {
  if (vl > r || vr < l) {
    return;
  }
  if (l <= vl && vr <= r) {
    st1[v].addLine(x);
    return;
  }
  add(v * 2, vl, (vl + vr) / 2, l, r, x);
  add(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r, x);
}
void reset() {
  for (int i = 0; i < 2 * ss; i++) {
    st[i].st.clear();
    st1[i].st.clear();
  }
}
long long get(int i, int x) {
  long long ans = -1e12;
  while (i) {
    chkmax(ans, st1[i].getmax(x));
    i >>= 1;
  }
  return ans;
}
long long f[MAXN];
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  while (ss < n) {
    ss <<= 1;
  }
  vector<int> st;
  for (int i = 0; i < n; i++) {
    while (!st.empty() && a[st.back()] <= a[i]) {
      st.pop_back();
    }
    ls[i] = (st.empty() ? 0 : st.back() + 1);
    st.push_back(i);
  }
  st.clear();
  for (int i = n - 1; i >= 0; i--) {
    while (!st.empty() && a[st.back()] <= a[i]) {
      st.pop_back();
    }
    rs[i] = (st.empty() ? n - 1 : st.back() - 1);
    st.push_back(i);
  }
  int maxs = 0;
  for (int i = 0; i < n; i++) {
    chkmax(maxs, a[i]);
    dp[i][0] = 1LL * maxs * (i + 1);
  }
  for (int j = 1; j < k; j++) {
    reset();
    for (int i = 0; i < n; i++) {
      f[i] = -getmax(1, 1, ss, max(1, ls[i]), i, a[i]);
      add(ss + i, Line(i, -dp[i][j - 1]));
    }
    vector<pair<Line, int> > sts;
    for (int i = 0; i < n; i++) {
      sts.push_back({Line(-a[i], -f[i]), i});
    }
    sort((sts).begin(), (sts).end());
    for (auto x : sts) {
      add(1, 1, ss, x.second + 1, rs[x.second] + 1, x.first);
    }
    for (int i = 0; i < n; i++) {
      dp[i][j] = -get(ss + i, i);
    }
  }
  cout << dp[n - 1][k - 1] << endl;
}