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;
void re(int& x);
template <class T, class... Ts>
void re(T& t, Ts&... ts);
void pr(long long x);
void pr(const char* x);
void ps();
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts);
int n, k;
int a[21000];
const long long oo = (long long)1e18;
long long dp[21000][110];
struct func_t {
  long long a, b;
  func_t(long long a = 0, long long b = oo) : a(a), b(b) {}
  long long query(long long x) const { return a * x + b; }
};
struct node_t {
  node_t *l, *r;
  func_t f;
  node_t(node_t* l = 0, node_t* r = 0, func_t f = func_t())
      : l(l), r(r), f(f) {}
  long long query(long long x) { return f.query(x); }
};
int used;
node_t nodes[1975893];
node_t* new_node() { return &nodes[used++]; }
node_t* upd(node_t* p, int l, int r, int L, int R, func_t f) {
  if (l > R || r < L) return p;
  int M = L + ((R - L) >> 1);
  node_t* res = new_node();
  *res = p ? node_t(p->l, p->r, p->f) : node_t();
  if (f.query(M) <= (p ? p->query(M) : oo)) swap(res->f, f);
  if (f.query(L) < res->query(L)) res->l = upd(res->l, l, r, L, M, f);
  if (f.query(R) < res->query(R)) res->r = upd(res->r, l, r, M + 1, R, f);
  return res;
}
long long query(node_t* p, int i, int L, int R) {
  if (!p) return oo;
  if (i < L || i > R) return oo;
  long long res = p->query(i);
  if (L < R) {
    res = min(res, query(p->l, i, L, (L + R) >> 1));
    res = min(res, query(p->r, i, ((L + R) >> 1) + 1, R));
  }
  return res;
}
node_t* merge(node_t* left, node_t* right, int lts, int lte, int rts, int rte,
              int part) {
  int ltsz = lte - lts + 1;
  int rtsz = rte - rts + 1;
  if (rtsz > ltsz) {
    swap(left, right);
    swap(lte, rte);
    swap(lts, rts);
  }
  for (int i = rts; i <= rte; i++) {
    left = upd(left, 0, 20000, 0, 20000, func_t{-i + 1, dp[i - 1][part - 1]});
  }
  return left;
}
int stam;
int fr[21000];
node_t* curhullAs[21000][110];
node_t* curhullBs[21000][110];
long long go() {
  for (int i = 1; i < (k + 1); ++i) dp[0][i] = oo;
  for (int i = 1; i < (n + 1); ++i) dp[i][0] = oo;
  for (int part = 1; part < (k + 1); ++part) {
    used = 0;
    stam = 0;
    for (int i = 1; i <= n; i++) {
      node_t* curhullA =
          upd(NULL, 0, 20000, 0, 20000, func_t{-i + 1, dp[i - 1][part - 1]});
      int up_to = i;
      while (stam && a[fr[stam - 1]] <= a[i]) {
        int lts = (stam >= 2 ? fr[stam - 2] + 1 : 1);
        curhullA = merge(curhullAs[stam - 1][part], curhullA, lts, up_to - 1,
                         up_to, i, part);
        up_to = lts;
        stam--;
      }
      curhullAs[stam][part] = curhullA;
      if (part <= i) {
        long long icp = query(curhullA, a[i], 0, 20000);
        curhullBs[stam][part] =
            upd(stam == 0 ? NULL : curhullBs[stam - 1][part], 0, 20000, 0,
                20000, func_t{a[i], icp});
        long long r = query(curhullBs[stam][part], i, 0, 20000);
        dp[i][part] = r;
      } else
        dp[i][part] = oo;
      fr[stam++] = i;
    }
  }
  return dp[n][k];
}
void solve() {
  re(n, k);
  for (int i = 1; i < (n + 1); ++i) re(a[i]);
  ps(go());
}
int main() { solve(); }
void re(int& x) { scanf("%d", &x); }
template <class T, class... Ts>
void re(T& t, Ts&... ts) {
  re(t);
  re(ts...);
}
void pr(long long x) { printf("%lld", x); }
void pr(const char* x) { printf("%s", x); }
void ps() { pr("\n"); }
template <class T, class... Ts>
void ps(const T& t, const Ts&... ts) {
  pr(t);
  if (sizeof...(ts)) pr(" ");
  ps(ts...);
}