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;
struct node {
  int a, b;
  node(int a = 0, int b = 1 << 30) : a(a), b(b) {}
  int get(int x) { return a * x + b; }
};
class Eins {
 public:
  vector<node> st;
  vector<int> a;
  int n;
  Eins(int l, int r) {
    n = r - l + 1;
    a.resize(n);
    for (int i = 0; i < n; i++) a[i] = i + l;
    st.resize(n << 2 | 1);
  }
  Eins(vector<int>& a) : a(a) {
    n = (int)a.size();
    st.resize(n << 2 | 1);
  }
  Eins() {}
  void clear() {
    for (auto& x : st) x = node();
  }
  void apply(vector<int>& b) {
    a = b;
    n = (int)a.size();
    st.resize(n << 2 | 1);
  }
  void modify(int id, int l, int r, node val) {
    int mid = l + r >> 1;
    if (st[id].get(a[mid]) > val.get(a[mid])) swap(st[id], val);
    if (l == r) return;
    if (st[id].get(a[l]) > val.get(a[l])) modify(id << 1, l, mid, val);
    if (st[id].get(a[r]) > val.get(a[r])) modify(id << 1 | 1, mid + 1, r, val);
  }
  void modify(int id, int l, int r, int L, int R, node val) {
    if (L <= a[l] && a[r] <= R) {
      modify(id, l, r, val);
      return;
    }
    int mid = l + r >> 1;
    if (L <= a[mid]) modify(id << 1, l, mid, L, R, val);
    if (R > a[mid]) modify(id << 1 | 1, mid + 1, r, L, R, val);
  }
  int get(int id, int l, int r, int val) {
    int ans = st[id].get(val);
    if (l == r) return ans;
    int mid = l + r >> 1;
    if (val <= a[mid]) return min(ans, get(id << 1, l, mid, val));
    return min(ans, get(id << 1 | 1, mid + 1, r, val));
  }
  int get(int id, int l, int r, int L, int R, int val) {
    if (L <= a[l] && a[r] <= R) return get(id, l, r, val);
    int mid = l + r >> 1;
    if (R <= a[mid]) return get(id << 1, l, mid, L, R, val);
    if (L > a[mid]) return get(id << 1 | 1, mid + 1, r, L, R, val);
    return min(get(id << 1, l, mid, L, R, val),
               get(id << 1 | 1, mid + 1, r, L, R, val));
  }
  int get(int val) { return get(1, 0, n - 1, val); }
  int get(int l, int r, int val) { return get(1, 0, n - 1, l, r, val); }
  void modify(int l, int r, node val) { modify(1, 0, n - 1, l, r, val); }
  void modify(node val) { modify(1, 0, n - 1, val); }
};
struct cvh {
  deque<node> d;
  bool cmp(node x, node y, node z) {
    return 1ll * (x.b - y.b) * (x.a - z.a) <= 1ll * (x.b - z.b) * (x.a - y.a);
  }
  void clear() { d.clear(); }
  void modify(node val) {
    while ((int)d.size() && val.a >= d.back().a) {
      val.b = min(val.b, d.back().b);
      d.pop_back();
    }
    while ((int)d.size() > 1 && cmp(d[d.size() - 2], d.back(), val))
      d.pop_back();
    d.emplace_back(val);
  }
  int get(int x) {
    if (d.empty()) return 1 << 30;
    int l = 0, r = (int)d.size() - 2, ans = r + 1;
    while (l <= r) {
      int mid = l + r >> 1;
      if (d[mid].get(x) <= d[mid + 1].get(x)) {
        r = mid - 1;
        ans = mid;
      } else
        l = mid + 1;
    }
    return d[ans].get(x);
  }
};
struct Zwei {
  vector<cvh> st;
  int n;
  Zwei(int n) : n(n) { st.resize((n + 1) << 2 | 1); }
  void clear() {
    for (auto& x : st) x.clear();
  }
  void modify(int id, int l, int r, int pos, node val) {
    st[id].modify(val);
    if (l == r) {
      return;
    }
    int mid = l + r >> 1;
    if (pos <= mid)
      modify(id << 1, l, mid, pos, val);
    else
      modify(id << 1 | 1, mid + 1, r, pos, val);
  }
  int get(int id, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
      return st[id].get(val);
    }
    int mid = l + r >> 1;
    int res = 1 << 30;
    if (L <= mid) res = get(id << 1, l, mid, L, R, val);
    if (R > mid) res = min(res, get(id << 1 | 1, mid + 1, r, L, R, val));
    return res;
  }
};
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, k;
  cin >> n >> k;
  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) cin >> a[i];
  deque<int> d;
  vector<int> l(n + 1);
  for (int i = 1; i <= n; i++) {
    while ((int)d.size() && a[d.back()] <= a[i]) d.pop_back();
    if (d.empty())
      l[i] = 0;
    else
      l[i] = d.back();
    d.emplace_back(i);
  }
  d.clear();
  vector<int> r(n + 1);
  for (int i = n; i >= 1; i--) {
    while ((int)d.size() && a[d.back()] <= a[i]) d.pop_back();
    if (d.empty())
      r[i] = n + 1;
    else
      r[i] = d.back();
    d.emplace_back(i);
  }
  vector<vector<int>> dp(n + 1, vector<int>(k + 1, 1 << 30));
  int mx = 0;
  Eins Tree(1, n);
  Zwei inq(n);
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[i]);
    dp[i][1] = mx * i;
  }
  for (int j = 2; j <= k; j++) {
    Tree.clear();
    inq.clear();
    for (int i = j - 1; i <= n; i++) {
      inq.modify(1, 0, n, i, node(-i, dp[i][j - 1]));
      int val = 1 << 30;
      for (int p = l[i]; p < i; p++) val = min(val, dp[p][j - 1] - a[i] * p);
      Tree.modify(i, r[i] - 1, node(a[i], inq.get(1, 0, n, l[i], i - 1, a[i])));
      if (i >= j) dp[i][j] = Tree.get(i);
    }
  }
  cout << dp[n][k];
}