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 read(int &x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void read(long long &x) {
  static char c;
  while (!isdigit(c = getchar()))
    ;
  x = c ^ 48;
  while (isdigit(c = getchar())) x = (x * 10) + (c ^ 48);
}
void chkmax(int &x, int y) {
  if (y > x) x = y;
}
void chkmin(int &x, int y) {
  if (y < x) x = y;
}
void chkmax(long long &x, long long y) {
  if (y > x) x = y;
}
void chkmin(long long &x, long long y) {
  if (y < x) x = y;
}
const int N = 5e4 + 10, Inf = 1e9;
int n, k;
int A[N];
int _lst[N];
namespace Cart {
int tot, _nd[N];
struct Node {
  int l, r, pos, son[2];
} t[N];
set<int> S;
pair<int, int> _[N];
void Build(int L) {
  S.clear(), tot = 0, memset(_nd, 0, sizeof _nd);
  S.insert(L), S.insert(n + 1), A[L] = A[n + 1] = Inf;
  for (int i = 1; i <= n - L; ++i) _[i] = make_pair(-A[i + L], i + L);
  sort(_ + 1, _ + n - L + 1);
  for (int i = 1; i <= n - L; ++i) {
    int pos = _[i].second;
    _nd[pos] = ++tot, t[tot].son[0] = t[tot].son[1] = 0;
    auto I = S.lower_bound(pos);
    int suf = *I, pre = *(--I);
    t[tot].l = pre + 1, t[tot].r = suf - 1, t[tot].pos = pos;
    if (A[suf] <= A[pre])
      t[_nd[suf]].son[0] = tot;
    else
      t[_nd[pre]].son[1] = tot;
    S.insert(pos);
  }
}
}  // namespace Cart
namespace LiChao {
struct Node {
  int k, b, f;
  Node() { k = f = 0, b = 1e9; }
  Node(int _k, int _b, int _f = 1) { k = _k, b = _b, f = _f; }
} t[N << 2];
int Line(int k, int b, int x) { return k * x + b; }
void Build(int now, int l, int r) {
  t[now] = Node();
  if (l == r) return;
  const int mid = (l + r) >> 1;
  Build((now << 1), l, mid), Build((now << 1 | 1), mid + 1, r);
}
void _Modify(int now, int l, int r, int k, int b) {
  const int mid = (l + r) >> 1;
  if (l == r) {
    if (!t[now].f) return t[now] = Node(k, b), void();
    if (Line(t[now].k, t[now].b, l) > Line(k, b, l)) t[now] = Node(k, b);
    return;
  }
  if (!t[now].f) return t[now] = Node(k, b), void();
  int _L1 = Line(t[now].k, t[now].b, l), _L2 = Line(k, b, l);
  int _R1 = Line(t[now].k, t[now].b, r), _R2 = Line(k, b, r);
  if (_L1 <= _L2 && _R1 <= _R2) return;
  if (_L2 <= _L1 && _R2 <= _R1) return t[now] = Node(k, b), void();
  int _m1 = Line(t[now].k, t[now].b, mid), _m2 = Line(k, b, mid);
  if (_m2 < _m1) swap(t[now].k, k), swap(t[now].b, b), swap(_L1, _L2);
  _L2 < _L1 ? _Modify((now << 1), l, mid, k, b)
            : _Modify((now << 1 | 1), mid + 1, r, k, b);
}
void Modify(int now, int l, int r, int x, int y, int k, int b) {
  const int mid = (l + r) >> 1;
  if (l >= x && r <= y) return _Modify(now, l, r, k, b);
  if (mid >= x) Modify((now << 1), l, mid, x, y, k, b);
  if (mid < y) Modify((now << 1 | 1), mid + 1, r, x, y, k, b);
}
int Query(int now, int l, int r, int pos) {
  if (l == r) return t[now].f ? Line(t[now].k, t[now].b, pos) : Inf;
  const int mid = (l + r) >> 1;
  int res = t[now].f ? Line(t[now].k, t[now].b, pos) : Inf;
  if (mid >= pos)
    return min(res, Query((now << 1), l, mid, pos));
  else
    return min(res, Query((now << 1 | 1), mid + 1, r, pos));
}
}  // namespace LiChao
deque<int> conv[N];
void Merge(int L, int R, int tar) {
  if (conv[L].size() < conv[R].size()) {
    swap(conv[tar], conv[R]);
    for (auto I = conv[L].rbegin(); I != conv[L].rend(); ++I) {
      while (conv[tar].size() > 1 &&
             1ll * (_lst[*I] - _lst[conv[tar][1]]) *
                     (conv[tar][0] - conv[tar][1]) >=
                 1ll * (_lst[conv[tar][0]] - _lst[conv[tar][1]]) *
                     (*I - conv[tar][1]))
        conv[tar].pop_front();
      conv[tar].push_front(*I);
    }
  } else {
    swap(conv[tar], conv[L]);
    for (auto I = conv[R].begin(); I != conv[R].end(); ++I) {
      while (conv[tar].size() > 1 &&
             1ll *
                     (_lst[conv[tar][conv[tar].size() - 1]] -
                      _lst[conv[tar][conv[tar].size() - 2]]) *
                     (*I - conv[tar][conv[tar].size() - 2]) >=
                 1ll * (_lst[*I] - _lst[conv[tar][conv[tar].size() - 2]]) *
                     (conv[tar][conv[tar].size() - 1] -
                      conv[tar][conv[tar].size() - 2]))
        conv[tar].pop_back();
      conv[tar].push_back(*I);
    }
  }
  conv[L].clear(), conv[R].clear();
}
void Insert(int d, int val) {
  while (conv[d].size() > 1 &&
         1ll *
                 (_lst[conv[d][conv[d].size() - 1]] -
                  _lst[conv[d][conv[d].size() - 2]]) *
                 (val - conv[d][conv[d].size() - 2]) >=
             1ll * (_lst[val] - _lst[conv[d][conv[d].size() - 2]]) *
                 (conv[d][conv[d].size() - 1] - conv[d][conv[d].size() - 2]))
    conv[d].pop_back();
  conv[d].push_back(val);
}
namespace TRANS {
void Calc(int now) {
  int l = Cart::t[now].l, r = Cart::t[now].r, p = Cart::t[now].pos, a = A[p];
  int ls = Cart::t[now].son[0], rs = Cart::t[now].son[1];
  if (ls) Calc(ls);
  if (rs) Calc(rs);
  while (conv[ls].size() > 1 && (_lst[conv[ls][1]] - _lst[conv[ls][0]]) <=
                                    a * (conv[ls][1] - conv[ls][0]))
    conv[ls].pop_front();
  int C = conv[ls].size() ? _lst[conv[ls][0]] - a * conv[ls][0] : Inf;
  chkmin(C, _lst[l - 1] - a * (l - 1));
  LiChao::Modify(1, 1, n, p, r, a, C);
  Insert(ls, p), Merge(ls, rs, now);
}
void Solve(int k) {
  Cart::Build(k - 1);
  for (int i = 0; i <= Cart::tot; ++i) conv[i].clear();
  LiChao::Build(1, 1, n);
  Calc(1);
  for (int i = 1; i <= n; ++i)
    _lst[i] = i > k ? LiChao::Query(1, 1, n, i) : Inf;
}
}  // namespace TRANS
void Work() {
  read(n), read(k);
  for (int i = 1; i <= n; ++i) read(A[i]);
  int M = 0;
  for (int i = 1; i <= n; ++i) chkmax(M, A[i]), _lst[i] = i * M;
  for (int i = 1; i < k; ++i) TRANS::Solve(i);
  printf("%d\n", _lst[n]);
}
int main() { Work(); }