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<vector<pair<Line, int> > > s(20005);
    int now = -1;
    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 (now != -1 && s[now].back().first.a <= A[j]) {
        int temp = s[now].back().second;
        s[now].pop_back();
        if (temp != now - 1 && now != 0) {
          s[now - 1].back().first.first =
              inter(s[now - 1].back().first, s[now].back().first);
        }
        now = temp;
      }
      Line l;
      l.a = a;
      l.b = b;
      l.first = 1e9;
      int last = now;
      while (now != -1) {
        Line ll = s[now].back().first;
        now--;
        ll.first = inter(ll, l);
        if (now != -1 && s[now].back().first.first >= ll.first) {
          continue;
        }
        now++;
        s[now].back().first.first = ll.first;
        break;
      }
      now++;
      s[now].push_back(make_pair(l, last));
      op = 1;
      int Max = now, Min = -1;
      while (Max > Min + 1) {
        int mid = (Max + Min) / 2;
        if (s[mid].back().first.first >= j) {
          Max = mid;
        } else {
          Min = mid;
        }
      }
      Line res = s[Max].back().first;
      dp[i][j] = res.a * j + res.b;
    }
    erase(root);
  }
  printf("%d\n", dp[k][n]);
}