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;
const int MAXN = 2e4 + 5;
const int MAXD = 1e2 + 5;
const int MAXP = (MAXN << 2) + MAXN * 15;
const long long linf = 0x3f3f3f3f3f3f3f3f;
template <typename T>
struct Linear_Hull {
  deque<T> *q;
  Linear_Hull(void) {}
  Linear_Hull(const T &x) {
    q = new deque<T>;
    q->push_back(x);
  }
  void create(const T &x) {
    q = new deque<T>;
    q->push_back(x);
  }
  void push_back(const T &x) {
    while ((int)q->size() >= 2) {
      T &lst = *(q->rbegin() + 1);
      if ((q->back().second - lst.second) * (lst.first - x.first) <
          (x.second - lst.second) * (lst.first - q->back().first))
        break;
      q->pop_back();
    }
    q->push_back(x);
  }
  void push_front(const T &x) {
    while ((int)q->size() >= 2) {
      T lst = *(q->begin() + 1);
      if ((q->front().second - lst.second) * (lst.first - x.first) >
          (x.second - lst.second) * (lst.first - q->front().first))
        break;
      q->pop_front();
    }
    q->push_front(x);
  }
  long long query(long long x) {
    int l = 0, r = (int)q->size() - 1;
    while (l < r) {
      int mid = (l + r + 1) >> 1;
      if (!mid || ((*q)[mid].second - (*q)[mid - 1].second) <=
                      x * ((*q)[mid - 1].first - (*q)[mid].first))
        l = mid;
      else
        r = mid - 1;
    }
    return (*q)[l].first * x + (*q)[l].second;
  }
  void merge_back(Linear_Hull &other) {
    if (other.q->size() <= q->size()) {
      for (int i = 0; i < (int)other.q->size(); ++i) push_back((*other.q)[i]);
      delete other.q;
    } else {
      for (int i = (int)q->size() - 1; i >= 0; --i) other.push_front((*q)[i]);
      delete q;
      q = other.q;
    }
  }
  void merge_front(Linear_Hull &other) {
    if (other.q->size() <= q->size()) {
      for (int i = (int)other.q->size() - 1; i >= 0; --i)
        push_front((*other.q)[i]);
      delete other.q;
    } else {
      for (int i = 0; i < (int)q->size(); ++i) other.push_back((*q)[i]);
      delete q;
      q = other.q;
    }
  }
};
struct Line {
  int k;
  long long b;
  Line(long long k = 0, long long b = 0) : k(k), b(b) {}
  inline void set_line(long long k_, long long b_) {
    k = k_;
    b = b_;
  }
  inline long long calc(const long long x) const { return k * x + b; }
};
struct Segment_Tree {
  Line *p[MAXP];
  int n, ls[MAXP], rs[MAXP], pcnt;
  Segment_Tree(void) : pcnt(0) {}
  inline void clear(void) { pcnt = 0; }
  void build(int n_, int &u, Line &k) {
    n = n_;
    build(u, 1, n, &k);
  }
  void build(int &u, int l, int r, Line *k) {
    p[u] = k;
    if (l == r) return;
    int mid = (l + r) >> 1;
    build(ls[u], l, mid, k);
    build(rs[u], mid + 1, r, k);
  }
  inline void update(int u, int &v, Line &k) { update(u, v, 1, n, &k); }
  void update(int u, int &v, int l, int r, Line *k) {
    bool wl = k->calc(l) < p[u]->calc(l), wr = k->calc(r) < p[u]->calc(r);
    if (!wl && !wr) {
      v = u;
      return;
    }
    v = ++pcnt;
    ls[v] = ls[u];
    rs[v] = rs[u];
    if (wl && wr) {
      p[v] = k;
      return;
    }
    int mid = (l + r) >> 1;
    if (k->calc(mid) < p[u]->calc(mid)) {
      if (k->k < p[u]->k)
        update(ls[u], ls[v], l, mid, p[u]);
      else
        update(rs[u], rs[v], mid + 1, r, p[u]);
      p[v] = k;
    } else {
      if (k->k < p[u]->k)
        update(rs[u], rs[v], mid + 1, r, k);
      else
        update(ls[u], ls[v], l, mid, k);
      p[v] = p[u];
    }
  }
  inline long long query(int u, int q) { return query(u, 1, n, q); }
  long long query(int u, int l, int r, int q) {
    if (l == r) return p[u]->calc(q);
    int mid = (l + r) >> 1;
    if (q <= mid)
      return min(p[u]->calc(q), query(ls[u], l, mid, q));
    else
      return min(p[u]->calc(q), query(rs[u], mid + 1, r, q));
  }
};
template <typename T>
struct Stack {
  T sta[MAXN];
  int tp;
  Stack(void) : tp(0) {}
  inline void clear(void) { tp = 0; }
  inline bool empty(void) { return !tp; }
  inline int size(void) { return tp; }
  inline T &top(void) { return sta[tp]; }
  inline void push(const T &x) { sta[++tp] = x; }
  inline void pop(void) { --tp; }
};
int a[MAXN];
long long f[2][MAXN];
int main(void) {
  int n, d;
  scanf("%d%d", &n, &d);
  for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
  for (int i = 1; i <= n; ++i) f[1][i] = max(f[1][i - 1], (long long)a[i]);
  for (int i = 1; i <= n; ++i) f[1][i] *= i;
  for (int k = 2; k <= d; ++k) {
    bool now = k & 1, lst = !now;
    static Stack<pair<int, Linear_Hull<pair<int, long long> > > > sta;
    static Line tmp[MAXN];
    static Segment_Tree tree;
    static int root[MAXN];
    sta.clear();
    tree.clear();
    tmp[0].set_line(0, linf);
    tree.build(n + 1, root[0], tmp[0]);
    for (int i = k; i <= n; ++i) {
      Linear_Hull<pair<int, long long> > cur(make_pair(-i, f[lst][i - 1]));
      while (!sta.empty() && sta.top().first <= a[i])
        cur.merge_front(sta.top().second), sta.pop();
      sta.push(make_pair(a[i], cur));
      tmp[sta.size()].set_line(a[i], cur.query(a[i]));
      tree.update(root[sta.size() - 1], root[sta.size()], tmp[sta.size()]);
      f[now][i] = tree.query(root[(int)sta.size()], i + 1);
    }
    for (int i = 1; i <= sta.size(); ++i) delete sta.sta[i].second.q;
  }
  printf("%lld\n", f[d & 1][n]);
  return 0;
}