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 {
  node *l, *r;
  vector<pair<int, pair<int, int>>> v;
  int a, b;
  node(int _a, int _b) : l(NULL), r(NULL), a(_a), b(_b) { v.clear(); }
} * root;
void build(node *n, int *dp) {
  vector<pair<int, pair<int, int>>> &v = n->v;
  for (int i = n->a; i <= n->b; i++) {
    while (!v.empty()) {
      auto p = v.back();
      v.pop_back();
      p.first = (p.second.second - dp[i]) / (-i - p.second.first);
      if (!v.empty() && v.back().first >= p.first) {
        continue;
      }
      v.push_back(p);
      break;
    }
    v.push_back(make_pair(1e9, make_pair(-i, dp[i])));
  }
  reverse(v.begin(), v.end());
  if (n->a == n->b) {
    return;
  }
  int mid = (n->a + n->b) / 2;
  n->l = new node(n->a, mid);
  n->r = new node(mid + 1, n->b);
  build(n->l, dp);
  build(n->r, dp);
}
int query(node *n, int l, int r, int k) {
  if (n->a >= l && n->b <= r) {
    while (n->v.back().first < k) {
      n->v.pop_back();
    }
    return n->v.back().second.first * k + n->v.back().second.second;
  }
  if (n->b < l || n->a > r) return 1e9;
  return min(query(n->l, l, r, k), query(n->r, l, r, k));
}
int dp[105][20005];
struct Line {
  int first, a, b;
};
int op;
bool operator<(const Line &l1, const Line &l2) {
  if (op) {
    return l1.first < l2.first;
  }
  return l1.a > l2.a;
}
int inter(Line l1, Line l2) { return (l2.b - l1.b) / (l1.a - l2.a); }
void erase(node *n) {
  if (!n) return;
  erase(n->l);
  erase(n->r);
  delete n;
}
int main() {
  int n, k;
  scanf("%d %d", &n, &k);
  int A[20005];
  for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
  int Max = 0;
  for (int i = 1; i <= n; i++) {
    Max = max(Max, A[i]);
    dp[1][i] = Max * i;
  }
  for (int i = 2; i <= k; i++) {
    root = new node(1, n);
    build(root, dp[i - 1]);
    vector<pair<int, int>> stk;
    stk.push_back(make_pair(1e9, i - 1));
    vector<Line> s;
    vector<vector<Line>> temp;
    for (int j = i; j <= n; j++) {
      while (stk.back().first <= A[j]) {
        stk.pop_back();
      }
      int a = A[j], b = query(root, stk.back().second, j - 1, A[j]);
      stk.push_back(make_pair(A[j], j));
      op = 0;
      while (!s.empty() && s.back().a <= A[j]) {
        s.pop_back();
      }
      Line l;
      l.a = a;
      l.b = b;
      l.first = 1e9;
      vector<Line> temp2;
      while (!temp.empty() && temp.back().back().a < s.back().a) {
        vector<Line> mytemp = temp.back();
        while (!mytemp.empty() && mytemp.back().a > l.a) {
          Line l = mytemp.back();
          l.first = 1e9;
          while (!s.empty()) {
            Line ll = s.back();
            s.pop_back();
            ll.first = inter(ll, l);
            if (!s.empty() && s.back().first >= ll.first) {
              temp2.push_back(ll);
              continue;
            }
            s.push_back(ll);
            break;
          }
          s.push_back(l);
          mytemp.pop_back();
        }
        temp.pop_back();
      }
      while (!s.empty()) {
        Line ll = s.back();
        s.pop_back();
        ll.first = inter(ll, l);
        if (!s.empty() && s.back().first >= ll.first) {
          temp2.push_back(ll);
          continue;
        }
        s.push_back(ll);
        break;
      }
      s.push_back(l);
      if (!temp2.empty()) temp.push_back(temp2);
      op = 1;
      auto it = lower_bound(s.begin(), s.end(), (Line){j, 0, 0});
      dp[i][j] = it->a * j + it->b;
    }
    erase(root);
  }
  printf("%d\n", dp[k][n]);
}