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;
int n, k;
int a[20010], L[20010], R[20010];
long long f[20010][110], dp[20010];
int p[20010];
struct line {
  long long a, b;
  line() {}
  line(int a, int b) { this->a = a, this->b = b; }
};
int bad(line l1, line l2, line l3) {
  return 1.0L * (l3.b - l1.b) / (l1.a - l3.a) <=
         1.0L * (l2.b - l1.b) / (l1.a - l2.a);
}
vector<line> cvL[100010], cvR[100010];
int ptrL[100010], ptrR[100010];
void add(int id, int l, int r, int i, line L) {
  if (i > r || i < l) return;
  while (cvL[id].size() && cvL[id].back().a == L.a && cvL[id].back().b >= L.b)
    cvL[id].pop_back();
  while (cvL[id].size() >= 2 && bad(*(-- --cvL[id].end()), cvL[id].back(), L))
    cvL[id].pop_back();
  cvL[id].push_back(L);
  ptrL[id] = min(ptrL[id], (int)cvL[id].size() - 1);
  if (l == r) return;
  int mid = l + r >> 1;
  add(id * 2, l, mid, i, L);
  add(id * 2 + 1, mid + 1, r, i, L);
}
long long get(int id, int l, int r, int u, int v, int x) {
  if (u > r || l > v) return 1e18;
  if (u <= l && r <= v) {
    if (cvL[id].empty()) return 1e18;
    while (ptrL[id] < cvL[id].size() - 1 &&
           1LL * cvL[id][ptrL[id]].a * x + cvL[id][ptrL[id]].b >
               1LL * cvL[id][ptrL[id] + 1].a * x + cvL[id][ptrL[id] + 1].b)
      ++ptrL[id];
    return 1LL * cvL[id][ptrL[id]].a * x + cvL[id][ptrL[id]].b;
  }
  int mid = l + r >> 1;
  return min(get(id * 2, l, mid, u, v, x),
             get(id * 2 + 1, mid + 1, r, u, v, x));
}
void add(int id, int l, int r, int u, int v, line L) {
  if (u > r || l > v) return;
  if (u <= l && r <= v) {
    while (cvR[id].size() && cvR[id].back().a == L.a && cvR[id].back().b >= L.b)
      cvR[id].pop_back();
    while (cvR[id].size() >= 2 && bad(*(-- --cvR[id].end()), cvR[id].back(), L))
      cvR[id].pop_back();
    cvR[id].push_back(L);
    ptrR[id] = min(ptrR[id], (int)cvR[id].size() - 1);
    return;
  }
  int mid = l + r >> 1;
  add(id * 2, l, mid, u, v, L);
  add(id * 2 + 1, mid + 1, r, u, v, L);
}
long long get(int id, int l, int r, int i, int x) {
  if (i > r || i < l) return 1e18;
  long long ans = 1e18;
  if (!cvR[id].empty()) {
    while (ptrR[id] < cvR[id].size() - 1 &&
           1LL * cvR[id][ptrR[id]].a * x + cvR[id][ptrR[id]].b >
               1LL * cvR[id][ptrR[id] + 1].a * x + cvR[id][ptrR[id] + 1].b)
      ++ptrR[id];
    ans = min(ans, 1LL * cvR[id][ptrR[id]].a * x + 1LL * cvR[id][ptrR[id]].b);
  }
  if (l == r) return ans;
  int mid = l + r >> 1;
  ans = min(ans, get(id * 2, l, mid, i, x));
  ans = min(ans, get(id * 2 + 1, mid + 1, r, i, x));
  return ans;
}
int main() {
  ios ::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) cin >> a[i];
  stack<int> stk;
  for (int i = 1; i <= n; ++i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      R[stk.top()] = i - 1;
      stk.pop();
    }
    stk.push(i);
  }
  while (!stk.empty()) {
    R[stk.top()] = n;
    stk.pop();
  }
  for (int i = n; i >= 1; --i) {
    while (!stk.empty() && a[stk.top()] < a[i]) {
      L[stk.top()] = i + 1;
      stk.pop();
    }
    stk.push(i);
  }
  while (!stk.empty()) {
    L[stk.top()] = 1;
    stk.pop();
  }
  for (int i = 1; i <= n; ++i) p[i] = i;
  sort(p + 1, p + n + 1,
       [&](int u, int v) { return (a[u] < a[v] || (a[u] == a[v] && u > v)); });
  for (int i = 1; i <= n; ++i) f[0][i] = 1e9;
  for (int _ = 1; _ <= k; ++_) {
    for (int i = 1; i <= n * 4; ++i)
      ptrL[i] = ptrR[i] = 0, cvL[i].clear(), cvR[i].clear();
    for (int i = 1; i <= n; ++i) add(1, 1, n, i, line(1 - i, f[_ - 1][i - 1]));
    for (int i = 1; i <= n; ++i)
      dp[p[i]] = get(1, 1, n, L[p[i]], p[i], a[p[i]]);
    for (int i = n; i >= 1; --i)
      add(1, 1, n, p[i], R[p[i]], line(a[p[i]], dp[p[i]]));
    for (int i = 1; i <= n; ++i) f[_][i] = get(1, 1, n, i, i);
  }
  cout << f[k][n];
}