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 N = 2e4 + 5;
int n, k, a[N], dp[N], h[N], d[N];
struct node {
  int k, b;
  inline node(int K, int B) : k(K), b(B) {}
  inline node() { k = 5e4, b = 1e9; }
  inline int operator()(const int& x) const { return k * x + b; }
};
namespace sgt {
node f[N << 2];
void add(int l, int r, int o, const int& L, const int& R, const node& g) {
  if (L <= l && r <= R) {
    int vL = g(l), vR = g(r);
    int nL = f[o](l), nR = f[o](r);
    if (nL <= vL && nR <= vR) return;
    if (nL >= vL && nR >= vR) {
      f[o] = g;
      return;
    }
  }
  if (l == r) return;
  const int mid = l + r >> 1;
  if (L <= mid) add(l, mid, o << 1, L, R, g);
  if (mid < R) add(mid + 1, r, o << 1 | 1, L, R, g);
}
inline int query(int l, int r, int o, const int& x) {
  if (l == r) return f[o](x);
  const int mid = l + r >> 1;
  int res = f[o](x);
  if (x <= mid) return min(res, query(l, mid, o << 1, x));
  return min(res, query(mid + 1, r, o << 1 | 1, x));
}
inline void rebuild(int l, int r, int o) {
  f[o] = node();
  if (l < r) {
    const int mid = l + r >> 1;
    rebuild(l, mid, o << 1), rebuild(mid + 1, r, o << 1 | 1);
  }
}
}  // namespace sgt
struct point {
  int x, y;
  inline point operator-(const point& rhs) const {
    return (point){x - rhs.x, y - rhs.y};
  }
} sta[N];
inline long long cross(const point& a, const point& b) {
  return (long long)a.x * b.y - (long long)a.y * b.x;
}
int top;
void insert(int x, int y) {
  point t = (point){x, y};
  while (top > 1 && cross(sta[top] - sta[top - 1], t - sta[top - 1]) <= 0)
    --top;
  sta[++top] = t;
}
inline int calc(const point& a, int L, int k) { return (a.x + L) * k + a.y; }
inline int binary(int len, int k) {
  int res = 0x3fffffff;
  if (top <= 20) {
    for (int i = 1; i <= top; ++i) res = min(res, calc(sta[i], len, k));
  } else {
    res = calc(sta[1], len, k);
    int l = 2, r = top, ans = 1;
    while (l <= r) {
      const int mid = l + r >> 1;
      int dlt = calc(sta[mid], len, k) - calc(sta[mid - 1], len, k);
      if (dlt < 0)
        l = (ans = mid) + 1;
      else
        r = mid - 1;
    }
    res = min(res, calc(sta[ans], len, k));
  }
  return res;
}
void solve(int l, int r) {
  if (l == r) {
    d[l] = min(d[l], dp[l - 1] + a[l]);
    return;
  }
  const int mid = l + r >> 1;
  solve(l, mid);
  solve(mid + 1, r);
  h[mid] = a[mid], h[mid + 1] = a[mid + 1];
  for (int i = mid - 1; i >= l; --i) h[i] = max(a[i], h[i + 1]);
  for (int i = mid + 2; i <= r; ++i) h[i] = max(a[i], h[i - 1]);
  int it = mid + 1;
  for (int i = mid; i >= l; --i) {
    while (it <= r && h[i] >= h[it]) ++it;
    int L = mid + 1, R = it - 1;
    if (L > R) continue;
    int k = h[i], b = dp[i - 1] + (L - i + 1) * k - L * k;
    sgt::add(1, n, 1, L, R, node(k, b));
  }
  top = 0;
  it = mid;
  for (int i = mid + 1; i <= r; ++i) {
    while (it >= l && h[it] < h[i]) insert(mid - it + 1, dp[it - 1]), --it;
    if (top) d[i] = min(d[i], binary(i - mid, h[i]));
  }
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; ++i) scanf("%d", a + i);
  for (int i = 1, mx = 0; i <= n; ++i) {
    mx = max(mx, a[i]);
    dp[i] = mx * i;
  }
  for (int t = 2; t <= k; ++t) {
    for (int i = 1; i <= n; ++i) d[i] = 2e9;
    solve(1, n);
    for (int i = 1; i <= n; ++i) dp[i] = min(d[i], sgt::query(1, n, 1, i));
    sgt::rebuild(1, n, 1);
  }
  printf("%d\n", dp[n]);
  return 0;
}