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 point {
  long long x, y;
  point(long long a = 0, long long b = 0) { x = a, y = b; }
  long long f(long long k) { return k * x + y; }
};
point operator-(point a, point b) { return point(a.x - b.x, a.y - b.y); }
point operator+(point a, point b) { return point(a.x + b.x, a.y + b.y); }
long long operator*(point a, point b) { return a.x * b.y - a.y * b.x; }
namespace lct {
point bst[30008 * 40];
int lc[30008 * 40], rc[30008 * 40];
int tot;
void init() { tot = 0; }
int newnode() {
  int p = ++tot;
  lc[p] = rc[p] = 0;
  return p;
}
vector<point> vp[30008 * 40];
void ins(int l, int r, int &rt, point p) {
  if (!rt) {
    rt = newnode();
    bst[rt] = p;
    return;
  }
  if (bst[rt].f((l + r) / 2) > p.f((l + r) / 2)) swap(p, bst[rt]);
  if (p.f(l) < bst[rt].f(l)) ins(l, (l + r) / 2, lc[rt], p);
  if (p.f(r) < bst[rt].f(r)) ins((l + r) / 2 + 1, r, rc[rt], p);
}
int merge(int l, int r, int x, int y) {
  if (!x or !y) return x + y;
  int p = newnode();
  if (bst[x].f((l + r) / 2) < bst[y].f((l + r) / 2)) {
    bst[p] = bst[x];
    if (bst[y].f(l) < bst[x].f(l)) ins(l, (l + r) / 2, lc[y], bst[y]);
    if (bst[y].f(r) < bst[x].f(r)) ins((l + r) / 2 + 1, r, rc[y], bst[y]);
  } else {
    bst[p] = bst[y];
    if (bst[x].f(l) < bst[y].f(l)) ins(l, (l + r) / 2, lc[x], bst[x]);
    if (bst[x].f(r) < bst[y].f(r)) ins((l + r) / 2 + 1, r, rc[x], bst[x]);
  }
  lc[p] = merge(l, (l + r) / 2, lc[x], lc[y]);
  rc[p] = merge((l + r) / 2 + 1, r, rc[x], rc[y]);
  return p;
}
long long ask(int x, int l, int r, int rt) {
  if (!rt) return 1e9;
  if (x <= (l + r) / 2)
    return min(bst[rt].f(x), ask(x, l, (l + r) / 2, lc[rt]));
  else
    return min(bst[rt].f(x), ask(x, (l + r) / 2 + 1, r, rc[rt]));
}
};  // namespace lct
long long dp[2][30008];
long long arr[30008];
long long n, K;
int now = 0;
struct deop {
  long long x;
  point p;
  long long top;
  deop(long long a = 0, point b = point(0, 0), long long c = 0) {
    x = a, p = b, top = c;
  }
};
point convex[30008];
long long top;
deop hull(point p) {
  if (!top) {
    int res = top + 1;
    deop o = deop(res, convex[res], top);
    top = res;
    convex[top] = p;
    return o;
  }
  int l = 2, r = top;
  int res = 1;
  while (l <= r) {
    int mid = (l + r) / 2;
    if ((convex[mid] - convex[mid - 1]) * (p - convex[mid]) <= 0)
      l = mid + 1, res = mid;
    else
      r = mid - 1;
  }
  res++;
  deop o = deop(res, convex[res], top);
  top = res;
  convex[top] = p;
  return o;
}
long long getans(long long k) {
  int l = 1, r = top;
  long long res = 1e9;
  while (l <= r) {
    int mid = (l + r) / 2;
    if (mid == 1) break;
    if (convex[mid].f(k) >= convex[mid - 1].f(k)) {
      res = min(res, convex[mid - 1].f(k));
      r = mid - 1;
    } else {
      res = min(res, convex[mid].f(k));
      l = mid + 1;
    }
  }
  if (l >= 1 and l <= top) res = min(res, convex[l].f(k));
  if (r >= 1 and r <= top) res = min(res, convex[r].f(k));
  return res;
}
deop kon[30008];
int rt[30008];
void process(deop d) {
  convex[d.x] = d.p;
  top = d.top;
}
void solve() {
  lct::init();
  top = 0;
  deque<int> dq;
  for (int i = 0; i <= n; i++) {
    dp[now][i] = getans(i);
    rt[i] = 0;
    lct::ins(1, 30008, rt[i], point(-i, dp[now ^ 1][i]));
    while (dq.size() and arr[1 + dq.back()] <= arr[i + 1])
      process(kon[dq.back()]),
          rt[i] = lct::merge(1, 30008, rt[i], rt[dq.back()]), dq.pop_back();
    dq.push_back(i);
    kon[i] = hull(point(arr[i + 1], lct::ask(arr[i + 1], 1, 30008, rt[i])));
  }
}
int main() {
  scanf("%lld%lld", &n, &K);
  for (int i = 1; i <= n; i++) scanf("%lld", &arr[i]);
  memset(dp, 0x3f, sizeof dp);
  dp[now][0] = 0;
  while (K--) now ^= 1, memset(dp[now], 0x3f, sizeof dp[now]), solve();
  printf("%lld\n", dp[now][n]);
  return 0;
}