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 n, K;
int a[20007];
int q[20007][27];
void ST() {
  for (int i = 1; i <= n; i++) {
    q[i][0] = i;
  }
  for (int j = 1; j <= 20; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      if (a[q[i][j - 1]] > a[q[i + (1 << (j - 1))][j - 1]]) {
        q[i][j] = q[i][j - 1];
      } else {
        q[i][j] = q[i + (1 << (j - 1))][j - 1];
      }
    }
  }
  return;
}
inline int ask(const int &op, const int &ed) {
  int l = log2(ed - op + 1);
  if (a[q[op][l]] > a[q[ed - (1 << l) + 1][l]]) {
    return q[op][l];
  } else {
    return q[ed - (1 << l) + 1][l];
  }
}
struct Line {
  long long k, b;
  Line(long long K = 0, long long B = 0) {
    k = K;
    b = B;
  }
};
Line tr[20007 << 2];
int vis[20007 << 2];
void build(int k, int l, int r) {
  vis[k] = 0;
  tr[k] = Line(0, 0);
  if (l == r) return;
  int mid = (l + r) >> 1;
  build((k << 1), l, mid);
  build((k << 1 | 1), mid + 1, r);
}
void pushdown(int k, int l, int r, Line s) {
  if (!vis[k]) return (void)(vis[k] = 1, tr[k] = s);
  long long l1 = s.k * l + s.b, r1 = s.k * r + s.b;
  long long l2 = tr[k].k * l + tr[k].b, r2 = tr[k].k * r + tr[k].b;
  if (l1 <= l2 && r1 <= r2) return (void)(tr[k] = s);
  if (l1 >= l2 && r1 >= r2) return;
  double pos = (s.b - tr[k].b) / (tr[k].k - s.k);
  int mid = (l + r) >> 1;
  if (pos <= mid)
    pushdown((k << 1), l, mid, r1 < r2 ? tr[k] : s);
  else
    pushdown((k << 1 | 1), mid + 1, r, l1 < l2 ? tr[k] : s);
  if ((pos <= mid && r1 < r2) || (pos > mid && l1 < l2)) tr[k] = s;
}
void insert(int k, int l, int r, int x, int y, Line s) {
  if (x <= l && r <= y) return pushdown(k, l, r, s);
  int mid = (l + r) >> 1;
  if (x <= mid) insert((k << 1), l, mid, x, y, s);
  if (y > mid) insert((k << 1 | 1), mid + 1, r, x, y, s);
}
long long query(int k, int l, int r, int x) {
  long long ret = tr[k].k * x + tr[k].b;
  if (!vis[k]) ret = 0x3f3f3f3f3f3f3f3f;
  if (l == r) return ret;
  int mid = (l + r) >> 1;
  if (x <= mid)
    ret = min(ret, query((k << 1), l, mid, x));
  else
    ret = min(ret, query((k << 1 | 1), mid + 1, r, x));
  return ret;
}
struct Point {
  long long x, y;
  Point(){};
  Point(long long a, long long b) : x(a), y(b){};
};
inline double Slope(const Point &a, const Point &b) {
  return 1.0 * (b.y - a.y) / (b.x - a.x);
}
deque<Point> empty;
deque<Point> tmp[20007];
int ls[20007], top;
Line query(int id, long long k) {
  if (!tmp[id].size()) return Line(0, 1e9);
  while (tmp[id].size() > 1 && Slope(tmp[id][0], tmp[id][1]) <= k)
    tmp[id].pop_front();
  return Line(k, tmp[id][0].y - k * tmp[id][0].x);
}
void insertfront(int id, Point a) {
  while (tmp[id].size() > 1) {
    Point x = tmp[id][0], y = tmp[id][1];
    if (Slope(a, y) >= Slope(x, y))
      tmp[id].pop_front();
    else
      break;
  }
  tmp[id].push_front(a);
  return;
}
void insertback(int id, Point a) {
  while (tmp[id].size() > 1) {
    int n = tmp[id].size();
    Point x = tmp[id][n - 2], y = tmp[id][n - 1];
    if (Slope(a, x) <= Slope(x, y))
      tmp[id].pop_back();
    else
      break;
  }
  tmp[id].push_back(a);
  return;
}
long long dp[107][20007];
int solve(int l, int r, const int &cur) {
  if (l > r) return -1;
  if (l == r) {
    int id = ls[top--];
    tmp[id].push_back(Point(l, dp[cur - 1][l]));
    return id;
  }
  int pos = ask(l + 1, r);
  int L = solve(l, pos - 1, cur);
  insert(1, 1, n, pos, r, query(L, a[pos]));
  if (L == -1) L = ls[top--];
  dp[cur][pos] = query(1, 1, n, pos);
  int R = solve(pos, r, cur);
  if (tmp[R].size() <= tmp[L].size()) {
    while (tmp[R].size()) {
      insertback(L, tmp[R][0]);
      tmp[R].pop_front();
    }
    ls[++top] = R;
    return L;
  } else {
    while (tmp[L].size()) {
      insertfront(R, tmp[L][tmp[L].size() - 1]);
      tmp[L].pop_back();
    }
    ls[++top] = L;
    return R;
  }
}
int main() {
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; i++) {
    ls[i] = i;
  }
  top = n;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
  }
  ST();
  for (int i = 1; i <= n; i++) {
    dp[1][i] = 1ll * i * a[ask(1, i)];
  }
  for (int i = 2; i <= K; i++) {
    build(1, 1, n);
    solve(i - 1, n, i);
  }
  printf("%lld\n", dp[K][n]);
  return 0;
}