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;
inline int read() {
  int w = 0, x = 0;
  char c = getchar();
  while (!isdigit(c)) w |= c == '-', c = getchar();
  while (isdigit(c)) x = x * 10 + (c ^ 48), c = getchar();
  return w ? -x : x;
}
namespace star {
const int maxn = 2e4 + 10, maxm = maxn * 32;
int n, m, mx, a[maxn], b[maxn], f[maxn], g[maxn], st[maxn], top;
int tot, ls[maxm], rs[maxm], e[maxm], rt[maxn];
inline int fw(int x, int i) { return i * a[x] + b[x]; }
inline bool cmp(int x, int y, int i) { return fw(x, i) > fw(y, i); }
void update(int& a, int b, int x, int l = 1, int r = n) {
  a = ++tot;
  ls[a] = ls[b], rs[a] = rs[b], e[a] = e[b];
  if (l == r) return;
  if (cmp(e[a], x, ((l + r) >> 1))) swap(e[a], x);
  if (cmp(e[a], x, l)) update(ls[a], ls[b], x, l, ((l + r) >> 1));
  if (cmp(e[a], x, r)) update(rs[a], rs[b], x, ((l + r) >> 1) + 1, r);
}
int query(int ro, int x, int l = 1, int r = n) {
  if (l == r or !ro) return fw(e[ro], x);
  return min(fw(e[ro], x), x <= ((l + r) >> 1)
                               ? query(ls[ro], x, l, ((l + r) >> 1))
                               : query(rs[ro], x, ((l + r) >> 1) + 1, r));
}
deque<int> q[maxn];
inline void merge(deque<int>& a, deque<int>& b) {
  if (a.size() > b.size())
    while (b.size()) {
      while (a.size() > 1 and 1ll * (g[a[1]] - g[a[0]]) * (a[0] - b.back()) <=
                                  1ll * (g[a[0]] - g[b.back()]) * (a[1] - a[0]))
        a.pop_front();
      a.push_front(b.back()), b.pop_back();
    }
  else {
    swap(a, b);
    int tl = a.size() - 1;
    while (b.size()) {
      while (tl and 1ll * (g[b.front()] - g[a[tl]]) * (a[tl] - a[tl - 1]) <=
                        1ll * (g[a[tl]] - g[a[tl - 1]]) * (b.front() - a[tl]))
        a.pop_back(), --tl;
      a.push_back(b.front()), b.pop_front(), ++tl;
    }
  }
}
inline int query(const deque<int>& a, int k) {
  int l = 0, r = a.size() - 1;
  while (l < r)
    g[a[((l + r) >> 1) + 1]] - g[a[((l + r) >> 1)]] <
            1ll * k*(a[((l + r) >> 1) + 1] - a[((l + r) >> 1)])
        ? (l = ((l + r) >> 1) + 1)
        : (r = ((l + r) >> 1));
  return g[a[((l + r) >> 1)]] - a[((l + r) >> 1)] * k;
}
inline void work() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) f[i] = i * (mx = max(mx, a[i] = read()));
  b[0] = 2e9;
  for (int i = 2; i <= m; i++) {
    memcpy(g, f, sizeof g);
    tot = top = 0;
    for (int j = i; j <= n; j++) {
      q[j].clear(), q[j].push_back(j - 1);
      while (top and a[st[top]] < a[j]) merge(q[j], q[st[top--]]);
      b[j] = query(q[j], a[j]);
      update(rt[j], rt[st[top]], j);
      st[++top] = j, f[j] = query(rt[j], j);
    }
  }
  printf("%d\n", f[n]);
}
}  // namespace star
signed main() {
  star::work();
  return 0;
}