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 std::min;
using std::swap;
const int maxn = 2e4 + 5;
int n, k, a[maxn];
int st[maxn], top;
long long dp[maxn], pdp[maxn];
int lcnt;
struct Line {
  int k;
  long long b;
  Line(int K = 0, long long B = 0) : k(K), b(B){};
  long long val(int x) { return 1ll * k * x + b; }
} L[maxn << 1];
int rt[maxn], ch[maxn * 20][2], Lid[maxn * 20], tot;
void clear() {
  memset(rt, 0, sizeof(rt));
  for (int i = 1; i <= tot; ++i) ch[i][0] = ch[i][1] = Lid[i] = 0;
  tot = 0;
}
struct Op {
  int t, p, x;
};
int optop, tim;
Op opst[maxn * 20];
void ins(int &u, int l, int r, int id, int ty) {
  if (!u)
    return Lid[u = ++tot] = id, (ty ? opst[++optop] = (Op){tim, u, 0} : Op()),
                   void();
  if (l == r)
    return (L[Lid[u]].val(l) > L[id].val(l)
                ? ((ty ? opst[++optop] = (Op){tim, u, Lid[u]} : Op()),
                   Lid[u] = id)
                : 0),
           void();
  int mid = l + r >> 1;
  if (L[Lid[u]].val(mid) < L[id].val(mid))
    L[Lid[u]].k < L[id].k ? ins(ch[u][0], l, mid, id, ty)
                          : ins(ch[u][1], mid + 1, r, id, ty);
  else
    (L[Lid[u]].k < L[id].k ? ins(ch[u][1], mid + 1, r, Lid[u], ty)
                           : ins(ch[u][0], l, mid, Lid[u], ty)),
        (ty ? opst[++optop] = (Op){tim, u, Lid[u]} : Op()), Lid[u] = id;
}
int merge(int A, int B, int l, int r) {
  if (!A || !B) return A + B;
  if (l == r)
    return Lid[A] = (L[Lid[A]].val(l) < L[Lid[B]].val(l) ? Lid[A] : Lid[B]), A;
  int mid = l + r >> 1;
  if (L[Lid[A]].val(mid) > L[Lid[B]].val(mid)) swap(Lid[A], Lid[B]);
  ch[A][0] = merge(ch[A][0], ch[B][0], l, mid),
  ch[A][1] = merge(ch[A][1], ch[B][1], mid + 1, r), ins(A, l, r, Lid[B], 0);
  return A;
}
long long qrymin(int u, int l, int r, int p) {
  if (!u) return LLONG_MAX;
  int mid = l + r >> 1;
  return min(L[Lid[u]].val(p), (p <= mid ? qrymin(ch[u][0], l, mid, p)
                                         : qrymin(ch[u][1], mid + 1, r, p)));
}
int main() {
  scanf("%d %d", &n, &k), L[0] = Line(0, LLONG_MAX);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  memset(pdp, 0x3f, sizeof(pdp)), pdp[0] = 0;
  for (int R = 1; R <= k; ++R) {
    clear(), top = lcnt = optop = 0;
    for (int i = 1; i <= n; ++i) {
      int now = i, nowval = a[i];
      L[++lcnt] = Line(-(i - 1), pdp[i - 1]), ins(rt[i], 1, 2e4, lcnt, 0);
      while (top && a[st[top]] < a[i]) {
        while (optop && opst[optop].t == st[top])
          Lid[opst[optop].p] = opst[optop].x, --optop;
        rt[i] = merge(rt[i], rt[st[top]], 1, 2e4), --top;
      }
      L[++lcnt] = Line(a[i], qrymin(rt[i], 1, 2e4, a[i])), tim = st[++top] = i,
      ins(rt[0], 1, n, lcnt, 1);
      dp[i] = qrymin(rt[0], 1, n, i);
    }
    memcpy(pdp, dp, sizeof(dp));
  }
  return printf("%lld\n", dp[n]), 0;
}