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>
#pragma GCC optimize("Ofast,inline,unroll-loops,fast-math")
using namespace std;
class Point {
 public:
  int x;
  int y;
  Point(int _x = 0, int _y = 0) : x(_x), y(_y) { return; }
  Point operator-(Point that) {
    return Point(this->x - that.x, this->y - that.y);
  }
  long long Cross(Point that) {
    return (long long)this->x * that.y - (long long)this->y * that.x;
  }
  int Eval(int p) { return x * p + y; }
};
int n, f[102][20002];
pair<int, int> q[15][20002];
deque<Point> g[20002 << 1];
Point h[20002 << 2];
void InitSegment(int x, int l, int r) {
  int m;
  h[x] = Point(0, INT_MAX >> 2);
  if (l == r) return;
  m = (l + r) >> 1;
  InitSegment(x << 1, l, m);
  InitSegment(x << 1 | 1, m + 1, r);
  return;
}
void InsertSegment(int x, int l, int r, int s, int t, Point v) {
  int m, p[3], q[3];
  if (l > t || r < s) return;
  if (l >= s && r <= t) {
    m = (l + r) >> 1;
    p[0] = v.Eval(l);
    p[1] = v.Eval(r);
    p[2] = v.Eval(m);
    q[0] = h[x].Eval(l);
    q[1] = h[x].Eval(r);
    q[2] = h[x].Eval(m);
    if (l == r) {
      if (p[0] <= q[0]) h[x] = v;
    } else {
      if (p[0] <= q[0] && p[1] <= q[1]) {
        h[x] = v;
        return;
      }
      if (p[0] > q[0] && p[1] > q[1]) return;
      if (p[0] <= q[0])
        if (p[2] <= q[2]) {
          InsertSegment(x << 1 | 1, m + 1, r, s, t, h[x]);
          h[x] = v;
        } else
          InsertSegment(x << 1, l, m, s, t, v);
      else if (p[2] <= q[2]) {
        InsertSegment(x << 1, l, m, s, t, h[x]);
        h[x] = v;
      } else
        InsertSegment(x << 1 | 1, m + 1, r, s, t, v);
    }
    return;
  }
  m = (l + r) >> 1;
  InsertSegment(x << 1, l, m, s, t, v);
  InsertSegment(x << 1 | 1, m + 1, r, s, t, v);
  return;
}
int MinSegment(int x, int l, int r, int p) {
  int m, o;
  if (l > p || r < p) return INT_MAX >> 2;
  o = h[x].Eval(p);
  if (l == r) return o;
  m = (l + r) >> 1;
  o = min(
      o, min(MinSegment(x << 1, l, m, p), MinSegment(x << 1 | 1, m + 1, r, p)));
  return o;
}
Point Tangent(deque<Point> &f, Point v) {
  int l, m, r;
  for (l = -1, r = (signed)f.size() - 1; l + 1 < r;) {
    m = (l + r) / 2;
    if ((f[m + 1] - f[m]).Cross(v) > 0)
      l = m;
    else
      r = m;
  }
  return f[r];
}
int MaxRMQ(int l, int r) {
  int t;
  t = 31 - __builtin_clz(r - l + 1);
  return max(q[t][l], q[t][r - (1 << t) + 1]).second;
}
int DP(int &c, int l, int r, int *f) {
  int m;
  Point t;
  deque<Point> p, q;
  if (l == r) {
    g[c].clear();
    g[c].push_back(Point(l, f[l]));
    return c++;
  }
  m = MaxRMQ(l + 1, r);
  p.swap(g[DP(c, l, m - 1, f)]);
  t = Tangent(p, Point(1, ::q[0][m].first));
  InsertSegment(1, 0, n, m, r,
                Point(::q[0][m].first, t.y - t.x * ::q[0][m].first));
  q.swap(g[DP(c, m, r, f)]);
  if (p.size() > q.size()) {
    for (; !q.empty(); q.pop_front()) {
      for (; p.size() > 1 &&
             (p.back() - p[p.size() - 2]).Cross(q.front() - p.back()) < 0;
           p.pop_back())
        ;
      p.push_back(q.front());
    }
    g[c].swap(p);
  } else {
    for (; !p.empty(); p.pop_back()) {
      for (; q.size() > 1 && (q.front() - q[1]).Cross(p.back() - q.front()) > 0;
           q.pop_front())
        ;
      q.push_front(p.back());
    }
    g[c].swap(q);
  }
  return c++;
}
int main(void) {
  int k;
  int i, j, c;
  scanf("%d %d", &n, &k);
  for (i = 1; i <= n; i++) {
    scanf("%d", &q[0][i].first);
    q[0][i].second = i;
  }
  for (i = 1; i < 15; i++)
    for (j = 1; j + (1 << i) - 1 <= n; j++)
      q[i][j] = max(q[i - 1][j], q[i - 1][j + (1 << (i - 1))]);
  fill(f[0] + 1, f[0] + 20002, INT_MAX >> 2);
  for (i = 1; i <= k; i++) {
    InitSegment(1, 0, n);
    DP(c = 0, 0, n, f[i - 1]);
    for (j = 0; j <= n; j++) f[i][j] = MinSegment(1, 0, n, j);
  }
  printf("%d\n", f[k][n]);
  return 0;
}