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>
clock_t t = clock();
namespace my_std {
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T>
inline T rnd(T l, T r) {
  return uniform_int_distribution<T>(l, r)(rng);
}
template <typename T>
inline bool chkmax(T& x, T y) {
  return x < y ? x = y, 1 : 0;
}
template <typename T>
inline bool chkmin(T& x, T y) {
  return x > y ? x = y, 1 : 0;
}
template <typename T>
inline void read(T& t) {
  t = 0;
  char f = 0, ch = getchar();
  double d = 0.1;
  while (ch > '9' || ch < '0') f |= (ch == '-'), ch = getchar();
  while (ch <= '9' && ch >= '0') t = t * 10 + ch - 48, ch = getchar();
  if (ch == '.') {
    ch = getchar();
    while (ch <= '9' && ch >= '0') t += d * (ch ^ 48), d *= 0.1, ch = getchar();
  }
  t = (f ? -t : t);
}
template <typename T, typename... Args>
inline void read(T& t, Args&... args) {
  read(t);
  read(args...);
}
}  // namespace my_std
using namespace my_std;
int n, K;
int a[20202];
int ST[20202][25], lg2[20202];
void init() {
  for (int i = (1); i <= (n); i++) ST[i][0] = i;
  for (int j = (1); j <= (20); j++)
    for (int i = (1); i <= (n - (1 << j) + 1); i++)
      ST[i][j] = (a[ST[i][j - 1]] > a[ST[i + (1 << (j - 1))][j - 1]]
                      ? ST[i][j - 1]
                      : ST[i + (1 << (j - 1))][j - 1]);
  for (int i = (2); i <= (n); i++) lg2[i] = lg2[i >> 1] + 1;
}
int qmax(int l, int r) {
  int len = lg2[r - l + 1];
  return (a[ST[l][len]] > a[ST[r - (1 << len) + 1][len]]
              ? ST[l][len]
              : ST[r - (1 << len) + 1][len]);
}
struct Line {
  long long k, b;
  Line(long long K = 0, long long B = 0) { k = K, b = B; }
};
namespace SegmentTree {
Line tr[20202 << 2];
int vis[20202 << 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 add(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) {
    if (l1 > l2)
      add(k << 1, l, mid, tr[k]), tr[k] = s;
    else
      add(k << 1, l, mid, s);
  } else {
    if (l1 > l2)
      add(k << 1 | 1, mid + 1, r, s);
    else
      add(k << 1 | 1, mid + 1, r, tr[k]), tr[k] = s;
  }
}
void insert(int k, int l, int r, int x, int y, Line s) {
  if (x <= l && r <= y) return add(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 = 1e18;
  if (l == r) return ret;
  int mid = (l + r) >> 1;
  if (x <= mid)
    chkmin(ret, query(k << 1, l, mid, x));
  else
    chkmin(ret, query(k << 1 | 1, mid + 1, r, x));
  return ret;
}
}  // namespace SegmentTree
using SegmentTree::build;
using SegmentTree::insert;
using SegmentTree::query;
struct Point {
  long long x, y;
  Point(long long X = 0, long long Y = 0) { x = X, y = Y; }
};
double calcK(Point a, Point b) { return 1.0 * (b.y - a.y) / (b.x - a.x); }
deque<Point> empty;
deque<Point> tmp[20202];
int st[20202], top;
Line query(int id, long long k) {
  if (!tmp[id].size()) return Line(0, 1e9);
  while (tmp[id].size() > 1 && calcK(tmp[id][0], tmp[id][1]) <= k)
    tmp[id].pop_front();
  return Line(k, tmp[id][0].y - k * tmp[id][0].x);
}
void insertfrnt(int id, Point a) {
  while (tmp[id].size() > 1) {
    Point x = tmp[id][0], y = tmp[id][1];
    if (calcK(a, y) >= calcK(x, y))
      tmp[id].pop_front();
    else
      break;
  }
  tmp[id].push_front(a);
}
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 (calcK(a, x) <= calcK(x, y))
      tmp[id].pop_back();
    else
      break;
  }
  tmp[id].push_back(a);
}
long long dp[111][20202];
int cur;
int solve(int l, int r) {
  if (l == r) {
    int id = st[top--];
    tmp[id].push_back(Point(l, dp[cur - 1][l]));
    return id;
  }
  int pos = qmax(l + 1, r);
  int L = solve(l, pos - 1);
  Line s = query(L, a[pos]);
  insert(1, 1, n, pos, r, s);
  if (!L) L = st[top--];
  dp[cur][pos] = query(1, 1, n, pos);
  int R = solve(pos, r);
  if (tmp[L].size() >= tmp[R].size()) {
    while (tmp[R].size()) insertback(L, tmp[R][0]), tmp[R].pop_front();
    st[++top] = R;
    return L;
  } else {
    while (tmp[L].size())
      insertfrnt(R, tmp[L][(int)tmp[L].size() - 1]), tmp[L].pop_back();
    st[++top] = L;
    return R;
  }
}
int main() {
  read(n, K);
  for (int i = (1); i <= (n); i++) st[i] = i;
  top = n;
  for (int i = (1); i <= (n); i++) read(a[i]);
  init();
  for (int i = (1); i <= (n); i++) dp[1][i] = 1ll * i * a[qmax(1, i)];
  cur = 2;
  while (cur <= K) {
    build(1, 1, n), solve(cur - 1, n), ++cur;
  }
  cout << dp[K][n];
  return 0;
}