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;
int mx = 20005 - 1, n;
struct hh {
  long long a, b;
  long long operator[](int k) { return k * a + b; }
};
long long fk = 1e18;
struct tr {
  int rt[20005], ls[20005 * 40], rs[20005 * 40], tot;
  hh sum[20005 * 40];
  void update(int &p, int l, int r, hh s) {
    if (s.b == fk) return;
    if (!p) p = ++tot, sum[p] = sum[0];
    if (l == r) {
      if (sum[p][l] > s[l]) sum[p] = s;
      return;
    }
    int mid = (l + r) >> 1;
    if (sum[p].a > s.a) swap(sum[p], s);
    if (sum[p][mid] <= s[mid])
      update(ls[p], l, mid, s);
    else
      swap(sum[p], s), update(rs[p], mid + 1, r, s);
  }
  int merge(int p1, int p2, int l, int r) {
    if (!p1 || !p2) return p1 | p2;
    if (l == r) {
      if (sum[p1][l] < sum[p2][l]) return p1;
      return p2;
    }
    int mid = (l + r) >> 1;
    if (sum[p1].a > sum[p2].a) swap(sum[p1], sum[p2]);
    if (sum[p1][mid] <= sum[p2][mid])
      update(ls[p1], l, mid, sum[p2]);
    else
      swap(sum[p1], sum[p2]), update(rs[p1], mid + 1, r, sum[p2]);
    ls[p1] = merge(ls[p1], ls[p2], l, mid);
    rs[p1] = merge(rs[p1], rs[p2], mid + 1, r);
    return p1;
  }
  long long query(int p, int l, int r, int x) {
    long long w = sum[p][x];
    if (l == r) return w;
    int mid = (l + r) >> 1;
    if (x <= mid)
      return min(w, query(ls[p], l, mid, x));
    else
      return min(w, query(rs[p], mid + 1, r, x));
  }
  void clear() {
    for (int i = 1; i <= tot; ++i) ls[i] = rs[i] = 0;
    tot = 0;
    for (int i = 1; i <= n; ++i) rt[i] = 0;
  }
} tr1;
struct Tr {
  int rt[20005], ls[20005 * 40], rs[20005 * 40], tot;
  hh sum[20005 * 40];
  void update(int &p, int l, int r, hh s) {
    if (s.b == fk) return;
    sum[++tot] = sum[p];
    ls[tot] = ls[p];
    rs[tot] = rs[p];
    p = tot;
    if (l == r) {
      if (sum[p][l] > s[l]) sum[p] = s;
      return;
    }
    int mid = (l + r) >> 1;
    if (sum[p].a > s.a) swap(sum[p], s);
    if (sum[p][mid] <= s[mid])
      update(ls[p], l, mid, s);
    else
      swap(sum[p], s), update(rs[p], mid + 1, r, s);
  }
  long long query(int p, int l, int r, int x) {
    long long w = sum[p][x];
    if (l == r) return w;
    int mid = (l + r) >> 1;
    if (x <= mid)
      return min(w, query(ls[p], l, mid, x));
    else
      return min(w, query(rs[p], mid + 1, r, x));
  }
  void clear() {
    for (int i = 1; i <= tot; ++i) ls[i] = rs[i] = 0;
    tot = 0;
    for (int i = 1; i <= n; ++i) rt[i] = 0;
  }
} tr2;
int k, a[20005], sk[20005];
long long dp[20005], Dp[20005];
void solve() {
  int r = 0;
  tr1.sum[0] = tr2.sum[0] = (hh){0, fk};
  for (int i = 1; i <= n; ++i) {
    tr1.update(tr1.rt[i], 1, mx, (hh){-(i - 1), dp[i - 1]});
    while (r && a[sk[r]] <= a[i])
      tr1.rt[i] = tr1.merge(tr1.rt[i], tr1.rt[sk[r]], 1, mx), --r;
    long long w = tr1.query(tr1.rt[i], 1, mx, a[i]);
    tr2.rt[i] = tr2.rt[sk[r]];
    sk[++r] = i;
    tr2.update(tr2.rt[i], 1, n, (hh){a[i], w});
    Dp[i] = tr2.query(tr2.rt[i], 1, n, i);
  }
  for (int i = 1; i <= n; ++i) dp[i] = Dp[i];
  tr1.clear();
  tr2.clear();
}
int main() {
  scanf("%d%d", &n, &k);
  int s = 0;
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) s = max(s, a[i]), dp[i] = 1ll * s * i;
  for (int i = 1; i < k; ++i) solve();
  printf("%lld\n", dp[n]);
}