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 void open(const char *s) {}
namespace IO {
const int S = (1 << 20) + 10;
char buf[S], *H, *T;
inline char Get() {
  if (H == T) T = (H = buf) + fread(buf, 1, S, stdin);
  if (H == T) return -1;
  return *H++;
}
inline int rd() {
  static int x, f;
  x = 0;
  f = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') f = -1;
  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
  return f > 0 ? x : -x;
}
}  // namespace IO
using IO::rd;
const int N = 20010, Inf = 1e9;
struct L {
  int k, b;
  L(int k = 0, int b = 0) : k(k), b(b) {}
  int f(int x) { return k * x + b; }
} st[N];
int n, k, top, a[N], f[N], g[N], pre[N], suf[N];
bool cmp(L a, L b, L c) {
  return 1ll * (a.k - b.k) * (c.b - a.b) <= 1ll * (a.k - c.k) * (b.b - a.b);
}
void ins(L x) {
  while (top && x.k >= st[top].k) x.b = min(x.b, st[top--].b);
  while (top > 1 && cmp(st[top - 1], st[top], x)) --top;
  st[++top] = x;
}
int calc(int x) {
  if (!top) return Inf;
  int l = 1, r = top;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (st[mid].f(x) <= st[mid + 1].f(x))
      r = mid;
    else
      l = mid + 1;
  }
  return st[l].f(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 + 1] = 0;
  for (int i = mid; i >= l; i--) suf[i] = max(suf[i + 1], a[i]);
  pre[mid] = 0;
  for (int i = mid + 1; i <= r; i++) pre[i] = max(pre[i - 1], a[i]);
  top = 0;
  int j = l;
  for (int i = r; i >= mid + 1; i--) {
    while (j <= mid && suf[j + 1] >= pre[i])
      if (g[j++] < Inf) ins(L(suf[j], g[j - 1] - (j - 1) * suf[j]));
    f[i] = min(f[i], calc(i));
  }
  top = 0;
  j = mid;
  for (int i = mid + 1; i <= r; i++) {
    while (j >= l && suf[j + 1] <= pre[i])
      if (g[j--] < Inf) ins(L(j + 1, g[j + 1]));
    f[i] = min(f[i], calc(-pre[i]) + i * pre[i]);
  }
}
int main() {
  open("hh");
  n = rd();
  k = rd();
  for (int i = 1; i <= n; i++) a[i] = rd(), pre[i] = max(pre[i - 1], a[i]);
  for (int i = 1; i <= n; i++) f[i] = pre[i] * i;
  for (int i = 2; i <= k; i++) {
    memcpy(g, f, sizeof g);
    memset(f, 0x3f, sizeof f);
    solve(1, n);
  }
  cout << f[n];
  return 0;
}