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;
using P = array<ll, 2>;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
const int N = 2e4 + 5;
int n;
int k;
ll a[N];
ll dp[N];
ll tdp[N];
ll ccw(P a, P b, P c) {
  return a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]);
}
ll f(P p, ll x) { return p[0] * x + p[1]; }
struct hull {
  ll val;
  deque<P> dq;
  void add_right(P x) {
    while (int(dq.size()) >= 2 &&
           ccw(dq[int(dq.size()) - 2], dq[int(dq.size()) - 1], x) <= 0) {
      dq.pop_back();
    }
    dq.push_back(x);
  }
  void add_left(P x) {
    while (int(dq.size()) >= 2 && ccw(dq[1], dq[0], x) >= 0) {
      dq.pop_front();
    }
    dq.push_front(x);
  }
  ll query(ll x) {
    int lo = 0;
    int hi = int(dq.size()) - 1;
    while (lo < hi) {
      int mid = (lo + hi) / 2;
      if (f(dq[mid], x) < f(dq[mid + 1], x)) {
        hi = mid;
      } else {
        lo = mid + 1;
      }
    }
    return f(dq[lo], x);
  }
};
const int OFF = 1 << 15;
P line[2 * OFF];
stack<vector<pair<int, P>>> pers;
void add_line(P nw, int v = 1, int l = 0, int r = OFF) {
  int m = (l + r) / 2;
  bool lef = f(nw, l) < f(line[v], l);
  bool mid = f(nw, m) < f(line[v], m);
  if (mid) {
    pers.top().push_back({v, line[v]});
    swap(line[v], nw);
  }
  if (r - l == 1) {
    return;
  } else if (lef != mid) {
    add_line(nw, 2 * v, l, m);
  } else {
    add_line(nw, 2 * v + 1, m, r);
  }
}
ll get(ll x, int v = 1, int l = 0, int r = OFF) {
  int m = (l + r) / 2;
  if (r - l == 1) {
    return f(line[v], x);
  } else if (x < m) {
    return min(f(line[v], x), get(x, 2 * v, l, m));
  } else {
    return min(f(line[v], x), get(x, 2 * v + 1, m, r));
  }
}
int main() {
  ios::sync_with_stdio(0), cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    dp[i] = 1e10;
  }
  for (int j = 1; j <= k; ++j) {
    for (int i = 1; i < 2 * OFF; ++i) {
      line[i] = {(ll)2e4, (ll)2e9};
    }
    stack<hull> stk;
    for (int i = j; i <= n; ++i) {
      hull h = {a[i], {{-(i - 1), dp[i - 1]}}};
      while (stk.size() && h.val >= stk.top().val) {
        hull &s = stk.top();
        if (int(s.dq.size()) >= int(h.dq.size())) {
          while (int(h.dq.size())) {
            s.add_left(h.dq.back());
            h.dq.pop_back();
          }
          swap(s.dq, h.dq);
        } else {
          while (int(s.dq.size())) {
            h.add_right(s.dq.front());
            s.dq.pop_front();
          }
        }
        for (auto [v, p] : pers.top()) {
          line[v] = p;
        }
        pers.pop();
        stk.pop();
      }
      pers.emplace();
      add_line({a[i], h.query(a[i])});
      stk.push(move(h));
      tdp[i] = get(i);
    }
    while (pers.size()) {
      pers.pop();
    }
    for (int i = 1; i <= n; ++i) {
      dp[i] = tdp[i];
    }
  }
  cout << dp[n] << '\n';
}