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 ll = long long;
template <typename T>
struct Line {
  T k, b;
  Line() {}
  Line(const Line<T>& _r) : k(_r.k), b(_r.b) {}
  Line(T _k, T _b) : k(_k), b(_b) {}
  inline T eval(T x) const { return k * x + b; }
  Line<T>& operator-=(const Line<T>& _r) {
    k -= _r.k;
    b -= _r.b;
    return *this;
  }
  friend Line<T> operator-(const Line<T>& _lhs, const Line<T>& _rhs) {
    return Line<T>(_lhs) -= _rhs;
  }
  inline T cross(const Line<T>& _r) const { return k * _r.b - b * _r.k; }
};
template <typename T>
T bs_last(T l, T r, function<bool(T)> f) {
  assert(l < r);
  T mid;
  while (l != r) {
    mid = l + (r - l) / 2;
    if (f(mid)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return r - 1;
}
template <typename T>
struct Convex {
  vector<Line<T>> hull;
  inline void add_line(T k, T b) {
    Line<T> ln(k, b);
    while (true) {
      int sz = size();
      if (!sz) break;
      if (sz == 1) {
        if (ln.k == hull[0].k && ln.b > hull[0].b) {
          hull.pop_back();
        }
        break;
      } else {
        T c = (ln - hull.back()).cross(ln - *(hull.rbegin() + 1));
        if (c >= 0)
          hull.pop_back();
        else
          break;
      }
    }
    hull.push_back(ln);
  }
  inline T query(T x) {
    int id = bs_last<int>(0, (int)hull.size(), [&](int i) {
      if (i == 0) return true;
      return hull[i].eval(x) >= hull[i - 1].eval(x);
    });
    return hull[id].eval(x);
  }
  size_t size() const { return hull.size(); }
  bool empty() const { return hull.empty(); }
};
void maxi(ll& x, ll y) {
  if (x < y) x = y;
}
using Ch = Convex<long long>;
const ll NINF = -(1e9);
string to_string(string s) { return '"' + s + '"'; }
string to_string(bool x) { return (x ? "T" : "F"); }
string to_string(const char* s) { return to_string((string)s); }
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename V>
string to_string(V v) {
  bool f = true;
  string res = "[";
  for (const auto& x : v) {
    if (!f) res += ", ";
    f = false;
    res += to_string(x);
  }
  res += "]";
  return res;
}
void debug() { cerr << endl; }
template <typename H, typename... T>
void debug(H h, T... t) {
  cerr << " " << to_string(h);
  debug(t...);
}
void solve() {
  int n, k;
  cin >> n >> k;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  vector<ll> dp(n + 1, NINF), nxt(n + 1);
  dp[0] = 0;
  vector<ll> L(n + 1), R(n + 1);
  function<void(int, int)> divi = [&](int l, int r) {
    if (r - l < 2) return;
    int m = (l + r) / 2;
    divi(l, m);
    divi(m, r);
    L[m] = NINF;
    for (int i = m - 1; i >= l; i--) {
      L[i] = max(L[i + 1], a[i]);
    }
    R[m] = a[m - 1];
    for (int i = m + 1; i < r; i++) {
      R[i] = max(R[i - 1], a[i - 1]);
    }
    2020;
    {
      Ch hull;
      for (int j = m, i = m - 1; j < r; j++) {
        while (i >= l && L[i] <= R[j]) {
          hull.add_line(i, dp[i]);
          i--;
        }
        if (!hull.empty()) maxi(nxt[j], hull.query(R[j]) - j * R[j]);
      }
    }
    {
      Ch hull;
      for (int j = r - 1, i = l; j >= m; j--) {
        while (i < m && L[i] >= R[j]) {
          hull.add_line(L[i], dp[i] + i * L[i]);
          i++;
        }
        if (!hull.empty()) maxi(nxt[j], hull.query(-j));
      }
    }
  };
  for (int _ = 0; _ < k; _++) {
    fill(nxt.begin(), nxt.end(), NINF);
    divi(0, n + 1);
    swap(dp, nxt);
    2020;
  }
  cout << -dp[n];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  solve();
  return 0;
}