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 gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
struct MergableHullNode {
  long long a, b;
  int prv, nxt;
  MergableHullNode() {}
  MergableHullNode(long long a, long long b) : a(a), b(b), prv(-1), nxt(-1) {}
  long long eval(long long x) {
    if (a == LLONG_MAX) return a;
    return a - b * x;
  }
};
struct MergableHull {
  static vector<MergableHullNode> nodes;
  static vector<int> pool;
  static int makenode(long long a, long long b) {
    if (((int)(pool).size()) > 0) {
      int ret = pool.back();
      pool.pop_back();
      nodes[ret] = MergableHullNode(a, b);
      return ret;
    } else {
      int ret = ((int)(nodes).size());
      nodes.push_back(MergableHullNode(a, b));
      return ret;
    }
  }
  static void releasenode(int a) { pool.push_back(a); }
  int head, tail;
  long long maxquery;
  MergableHull() : head(-1), tail(-1), maxquery(LLONG_MIN) {}
  void init(long long a, long long b) { head = tail = makenode(a, b); }
  void popback() {
    int a = tail;
    assert(a != -1);
    if (nodes[a].prv == -1) {
      assert(head == a);
      head = -1;
    } else
      nodes[nodes[a].prv].nxt = -1;
    tail = nodes[a].prv;
    releasenode(a);
  }
  void popfront() {
    int a = head;
    assert(a != -1);
    if (nodes[a].nxt == -1) {
      assert(tail == a);
      tail = -1;
    } else
      nodes[nodes[a].nxt].prv = -1;
    head = nodes[a].nxt;
    releasenode(a);
  }
  long long query(long long x) {
    assert(x >= maxquery);
    maxquery = x;
    assert(head != -1);
    while (nodes[head].nxt != -1 &&
           nodes[nodes[head].nxt].eval(x) <= nodes[head].eval(x))
      popfront();
    return nodes[head].eval(x);
  }
  void releaseall() {
    for (int x = head; x != -1; x = nodes[x].nxt) releasenode(x);
  }
};
vector<MergableHullNode> MergableHull::nodes;
vector<int> MergableHull::pool;
long long divup(long long num, long long den) {
  if (den < 0) num = -num, den = -den;
  if (num >= 0)
    return (num + den - 1) / den;
  else
    return num / den;
}
long long overtake(int pidx, int qidx) {
  MergableHullNode p = MergableHull::nodes[pidx], q = MergableHull::nodes[qidx];
  assert(p.b > q.b);
  if (p.a == LLONG_MAX) {
    assert(q.a != LLONG_MAX);
    return LLONG_MIN;
  }
  if (q.a == LLONG_MAX) {
    assert(p.a != LLONG_MAX);
    return LLONG_MAX;
  }
  return divup(p.a - q.a, p.b - q.b);
}
MergableHull merge(MergableHull a, MergableHull b) {
  assert(a.head != -1 && a.tail != -1 && b.head != -1 && b.tail != -1);
  while (true) {
    bool change = false;
    if (MergableHull::nodes[a.tail].prv != -1 &&
        overtake(b.head, a.tail) <=
            overtake(a.tail, MergableHull::nodes[a.tail].prv)) {
      change = true;
      a.popback();
    }
    if (MergableHull::nodes[b.head].nxt != -1 &&
        overtake(MergableHull::nodes[b.head].nxt, b.head) <=
            overtake(b.head, a.tail)) {
      change = true;
      b.popfront();
    }
    if (!change) break;
  }
  MergableHull::nodes[a.tail].nxt = b.head;
  MergableHull::nodes[b.head].prv = a.tail;
  MergableHull ret;
  ret.head = a.head, ret.tail = b.tail,
  ret.maxquery = max(a.maxquery, b.maxquery);
  return ret;
}
const int MAXN = 20000;
const int MAXK = 100;
struct Opt {
  int lj, hj, mx, li, hi;
  vector<long long> vals;
  Opt() {}
  Opt(int lj, int hj, int mx, int li, int hi)
      : lj(lj), hj(hj), mx(mx), li(li), hi(hi) {}
};
int n, K;
int a[MAXN];
int stck[MAXN], nstck;
vector<Opt> opt;
vector<int> who[MAXN + 1];
long long dp[MAXN + 1][MAXK + 1];
vector<pair<int, MergableHull>> hull1[MAXK + 1];
void printhull(MergableHull h) {
  for (int x = h.head; x != -1; x = MergableHull::nodes[x].nxt) {
    if (x != h.head) printf(" ");
    printf("(%lld%c%lld*x[%d,%d])", MergableHull::nodes[x].a,
           MergableHull::nodes[x].b <= 0 ? '+' : '-',
           abs(MergableHull::nodes[x].b), MergableHull::nodes[x].prv,
           MergableHull::nodes[x].nxt);
  }
}
void process(int i) {
  for (int k = (0); k <= (K); ++k) {
    if (k != 0) {
      MergableHull cur;
      cur.init(dp[i][k], i);
      while (((int)(hull1[k]).size()) > 0 &&
             a[hull1[k][((int)(hull1[k]).size()) - 1].first] <= a[i]) {
        MergableHull oth = hull1[k][((int)(hull1[k]).size()) - 1].second;
        hull1[k].pop_back();
        cur = merge(oth, cur);
      }
      hull1[k].push_back(make_pair(i, cur));
    }
    for (int _ = (0); _ < (((int)(who[i]).size())); ++_) {
      int idx = who[i][_];
      if (k == 0) {
        opt[idx].vals[k] = opt[idx].lj == 0 ? 0 : LLONG_MAX;
        continue;
      }
      int l = ((int)(hull1[k]).size()) == 1
                  ? 0
                  : hull1[k][((int)(hull1[k]).size()) - 2].first + 1,
          h = hull1[k][((int)(hull1[k]).size()) - 1].first;
      assert(opt[idx].lj == l && opt[idx].hj == h);
      opt[idx].vals[k] =
          hull1[k][((int)(hull1[k]).size()) - 1].second.query(opt[idx].mx);
    }
  }
}
void rec(int li, int hi, vector<int> optidx) {
  vector<int> myidx, noptidx;
  for (int i = (0); i < (((int)(optidx).size())); ++i) {
    int idx = optidx[i];
    if (opt[idx].li <= li && hi <= opt[idx].hi)
      myidx.push_back(idx);
    else if (opt[idx].li <= hi && li <= opt[idx].hi)
      noptidx.push_back(idx);
  }
  for (int k = (1); k <= (K); ++k) {
    vector<int> curidx;
    for (int _ = (0); _ < (((int)(myidx).size())); ++_) {
      int idx = myidx[_];
      if (opt[idx].vals[k - 1] != LLONG_MAX) curidx.push_back(idx);
    }
    sort(curidx.begin(), curidx.end(), [&](int p, int q) {
      if (opt[p].mx != opt[q].mx) return opt[p].mx > opt[q].mx;
      return opt[p].vals[k - 1] < opt[q].vals[k - 1];
    });
    MergableHull hull2;
    for (int _ = (0); _ < (((int)(curidx).size())); ++_) {
      int idx = curidx[_], pidx = _ == 0 ? -1 : curidx[_ - 1];
      if (pidx != -1 && opt[pidx].mx == opt[idx].mx) continue;
      MergableHull cur;
      cur.init(opt[idx].vals[k - 1], -opt[idx].mx);
      if (_ == 0)
        hull2 = cur;
      else
        hull2 = merge(hull2, cur);
    }
    if (hull2.head != -1)
      for (int i = (li); i <= (hi); ++i)
        dp[i][k] = min(dp[i][k], hull2.query(i));
    hull2.releaseall();
  }
  if (li == hi) {
    process(li);
  } else {
    int mi = li + (hi - li) / 2;
    rec(li, mi, noptidx);
    rec(mi + 1, hi, noptidx);
  }
}
long long solve() {
  nstck = 0;
  opt.clear();
  for (int i = (0); i < (n); ++i) {
    while (nstck > 0 && a[i] >= a[stck[nstck - 1]]) {
      int idx = stck[--nstck];
      opt.push_back(
          Opt(nstck == 0 ? 0 : stck[nstck - 1] + 1, idx, a[idx], idx + 1, i));
    }
    stck[nstck++] = i;
  }
  while (nstck > 0) {
    int idx = stck[--nstck];
    opt.push_back(
        Opt(nstck == 0 ? 0 : stck[nstck - 1] + 1, idx, a[idx], idx + 1, n));
  }
  for (int i = (0); i < (((int)(opt).size())); ++i)
    opt[i].vals = vector<long long>(K + 1, -1LL);
  for (int i = (0); i <= (n); ++i) who[i].clear();
  for (int i = (0); i < (((int)(opt).size())); ++i) who[opt[i].hj].push_back(i);
  for (int k = (0); k <= (K); ++k) hull1[k].clear();
  for (int i = (0); i <= (n); ++i)
    for (int k = (0); k <= (K); ++k) dp[i][k] = i == 0 ? 0 : LLONG_MAX;
  process(0);
  vector<int> optidx;
  for (int i = (0); i < (((int)(opt).size())); ++i) optidx.push_back(i);
  rec(1, n, optidx);
  for (int k = (0); k <= (K); ++k)
    for (int j = (0); j < (((int)(hull1[k]).size())); ++j)
      hull1[k][j].second.releaseall();
  return dp[n][K];
}
void run() {
  scanf("%d%d", &n, &K);
  for (int i = (0); i < (n); ++i) scanf("%d", &a[i]);
  printf("%lld\n", solve());
}
long long solvestupid() {
  vector<vector<long long>> dp(n + 1, vector<long long>(K + 1, LLONG_MAX));
  for (int k = (0); k <= (K); ++k) dp[0][k] = 0;
  for (int i = (1); i <= (n); ++i)
    for (int k = (1); k <= (K); ++k)
      for (int j = (0); j < (i); ++j) {
        int mx = 0;
        for (int _ = (j); _ < (i); ++_) mx = max(mx, a[_]);
        if (dp[j][k - 1] != LLONG_MAX)
          dp[i][k] = min(dp[i][k], dp[j][k - 1] + (long long)(i - j) * mx);
      }
  return dp[n][K];
}
void stress() {
  int mxn = 10;
  for (int rep = (0); rep < (100000); ++rep) {
    n = rand() % mxn + 1, K = rand() % n + 1;
    for (int i = (0); i < (n); ++i) a[i] = rand() % 100;
    long long have = solve();
    long long want = solvestupid();
    if (have == want) {
      if (rep % 100 == 99) printf(".");
      continue;
    }
    printf("err in rep %d\n", rep);
    printf("have=%lld want=%lld\n", have, want);
    printf("%d %d\n", n, K);
    for (int i = (0); i < (n); ++i) {
      if (i != 0) printf(" ");
      printf("%d", a[i]);
    }
    puts("");
  }
}
void stresslarge() {
  for (int rep = (0); rep < (1); ++rep) {
    n = 20000, K = 100;
    for (int i = (0); i < (n); ++i) a[i] = n - i - 1;
    long long have = solve();
    printf("have=%lld\n", have);
  }
}
int main() {
  run();
  return 0;
}