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>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
namespace IO {
const int L = 1 << 15;
char ibuf[L | 1], *iS = ibuf, *iT = ibuf, obuf[L | 1], *oS = obuf,
                  *oT = obuf + L, c, st[66];
int tp = 0, f;
inline void flush() {
  fwrite(obuf, sizeof(char), oS - obuf, stdout);
  oS = obuf;
}
inline long long read() {
  long long x = 0;
  f = 1, c = getchar();
  for (; !isdigit(c); c = getchar())
    if (c == '-') f = -1;
  for (; isdigit(c); c = getchar()) x = (x << 1) + (x << 3) + (c & 15);
  return x * f;
}
inline void write(long long x) {
  if (!x) putchar('0');
  if (x < 0) putchar('-'), x = -x;
  while (x) st[++tp] = x % 10 + '0', x /= 10;
  while (tp) putchar(st[tp--]);
}
inline void writeln(long long x) {
  write(x);
  putchar('\n');
}
struct IOflusher {
  ~IOflusher() { flush(); }
} _ioflusher_;
}  // namespace IO
using IO::read;
using IO::write;
using IO::writeln;
const int maxn = 2e5 + 233;
struct L {
  long long b, k;
  L() {}
  L(long long b, long long k) : b(b), k(k) {}
  long long F(long long x) { return x * k + b; }
} q[maxn];
bool cmp(L x, L y, L z) {
  return 1ll * (x.b - y.b) * (x.k - z.k) <= 1ll * (x.b - z.b) * (x.k - y.k);
}
int top, n, k, f[maxn], g[maxn], a[maxn], t[maxn];
void insert(L x) {
  for (; top && x.k >= q[top].k; top--) x.b = min(x.b, q[top].b);
  for (; top > 1 && cmp(q[top - 1], q[top], x); top--)
    ;
  q[++top] = x;
}
int func(int x) {
  if (!top) return 1 << 30;
  int l = 1, r = top - 1, ans = top;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (q[mid].F(x) <= q[mid + 1].F(x))
      ans = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return q[ans].F(x);
}
void divide(int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  divide(l, mid), divide(mid + 1, r);
  t[mid] = a[mid], t[mid + 1] = a[mid + 1];
  for (register int i = (mid - 1); i >= int(l); --i) t[i] = max(t[i + 1], a[i]);
  for (register int i = (mid + 2); i <= int(r); ++i) t[i] = max(t[i - 1], a[i]);
  top = 0;
  for (int i = r, j = l; i > mid; --i) {
    for (; j <= mid && t[j + 1] >= t[i]; ++j)
      if (f[j] < 1 << 30) insert(L(f[j] - j * t[j + 1], t[j + 1]));
    g[i] = min(g[i], func(i));
  }
  top = 0;
  for (int i = mid + 1, j = mid; i <= r; ++i) {
    for (; j >= l && t[j + 1] <= t[i]; --j)
      if (f[j] < 1 << 30) insert(L(f[j], j));
    g[i] = min(g[i], func(-t[i]) + i * t[i]);
  }
}
int main() {
  n = read(), k = read();
  for (register int i = (1); i <= int(n); ++i) a[i] = read();
  for (register int i = (1); i <= int(n); ++i) f[i] = max(f[i - 1], a[i]);
  for (register int i = (1); i <= int(n); ++i) f[i] = i * f[i];
  for (register int i = (2); i <= int(k); ++i) {
    for (register int j = (0); j <= int(n); ++j) g[j] = 1 << 30;
    divide(1, n);
    for (register int j = (0); j <= int(n); ++j) f[j] = g[j];
  }
  writeln(f[n]);
  return 0;
}