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;
const int maxn = (int)1e5 + 100;
const int mod = (int)1e9 + 7;
const int P = (int)1e6 + 7;
const int inf = mod;
int n, k, a[maxn], suf[maxn], pref[maxn];
int dp[maxn], fdp[maxn];
struct line {
  int k, b;
  line(int _k, int _b) { k = _k, b = _b; }
  int val(int x) { return k * x + b; }
};
long double intersect(line l1, line l2) {
  return (long double)(l2.b - l1.b) / (l1.k - l2.k);
}
bool bad(line l1, line l2, line l3) {
  long double q1 = intersect(l1, l2);
  long double q2 = intersect(l1, l3);
  return q1 >= q2;
}
vector<line> v;
inline void add(line l) {
  int b = l.b;
  while ((int)v.size() && v.back().k == l.k)
    b = min(b, v.back().b), v.pop_back();
  l.b = b;
  while ((int)v.size() > 1 &&
         bad(v[(int)v.size() - 2], v[(int)v.size() - 1], l))
    v.pop_back();
  v.push_back(l);
}
int get(int x) {
  if (!(int)v.size()) return inf;
  int l = 0, res = 0, r = (int)v.size() - 1;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (v[mid].val(x) > v[mid + 1].val(x)) {
      l = mid + 1;
    } else {
      r = mid;
    }
  }
  return v[r].val(x);
}
void solve(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  suf[mid] = a[mid];
  for (int i = mid - 1; i >= l; i--) suf[i] = max(suf[i + 1], a[i]);
  pref[mid + 1] = a[mid + 1];
  for (int i = mid + 2; i <= r; i++) pref[i] = max(pref[i - 1], a[i]);
  v.clear();
  suf[mid + 1] = pref[mid] = 0;
  int ptr = l;
  for (int i = r; i >= mid + 1; i--) {
    while (ptr <= mid && suf[ptr + 1] >= pref[i]) {
      if (dp[ptr] != inf) add(line(suf[ptr + 1], dp[ptr] - ptr * suf[ptr + 1]));
      ptr++;
    }
    fdp[i] = min(fdp[i], get(i));
  }
  v.clear();
  ptr = mid;
  for (int i = mid + 1; i <= r; i++) {
    while (ptr >= l && suf[ptr + 1] <= pref[i]) {
      if (dp[ptr] != inf) add(line(ptr, dp[ptr]));
      ptr--;
    }
    fdp[i] = min(fdp[i], get(-pref[i]) + i * pref[i]);
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[i]);
    dp[i] = mx * i;
  }
  for (int step = 1; step <= k - 1; step++) {
    for (int i = 1; i <= n; i++) fdp[i] = inf;
    solve(1, n);
    for (int i = 1; i <= n; i++) dp[i] = fdp[i];
  }
  printf("%d", dp[n]);
}