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[20202];
signed long long from[20202];
signed long long to[20202];
int X[20202], Y[20202];
template <typename V>
struct ConvexHull {
  deque<pair<V, V>> Q;
  V calc(pair<V, V> p, V x) { return p.first * x + p.second; }
  int dodo(pair<V, V> A, pair<V, V> B, pair<V, V> C) {
    return ((A.second - C.second) * (B.first - A.first) <=
            (A.second - B.second) * (C.first - A.first));
  }
  void add(V a, V b) {
    if (Q.size() && Q.back().first == a) {
      if (b >= Q.back().second) return;
      Q.pop_back();
    }
    Q.push_back({a, b});
    int v;
    while ((v = Q.size()) >= 3 && dodo(Q[v - 3], Q[v - 2], Q[v - 1]))
      Q[v - 2] = Q[v - 1], Q.pop_back();
  }
  V query(V x) {
    if (Q.empty()) return 1LL << 30;
    int L = -1, R = Q.size() - 1;
    while (R - L > 1) {
      int M = (L + R) / 2;
      (((calc(Q[M], x) >= calc(Q[M + 1], x))) ? L : R) = M;
    }
    return calc(Q[R], x);
  }
};
void hoge(int L, int R) {
  if (L + 1 == R) return;
  int M = (L + R) / 2;
  hoge(L, M);
  hoge(M, R);
  int i;
  X[M - 1] = 0;
  Y[M] = 0;
  for (i = M - 1; i >= L; i--) Y[i] = max(Y[i + 1], A[i]);
  for (i = M; i < R; i++) X[i] = max(X[i - 1], A[i]);
  ConvexHull<signed long long> chtX, chtY;
  int cur = M - 1;
  for (i = M; i < R; i++) {
    while (cur >= L && Y[cur + 1] <= X[i]) {
      chtX.add(cur, from[cur]);
      cur--;
    }
    to[i] = min(to[i], chtX.query(-X[i]) + i * X[i]);
  }
  cur = L;
  for (i = R - 1; i >= M; i--) {
    while (cur < M && Y[cur + 1] >= X[i]) {
      chtY.add(Y[cur + 1], from[cur] - Y[cur + 1] * cur);
      cur++;
    }
    to[i] = min(to[i], chtY.query(i));
  }
}
void solve() {
  int i, j, k, l, r, x, y;
  string s;
  cin >> N >> K;
  for (i = 0; i < (N); i++) {
    cin >> A[i + 1];
    from[i + 1] = 1LL << 30;
  }
  while (K--) {
    for (i = 0; i < (N + 1); i++) to[i] = 1LL << 30;
    hoge(0, N + 1);
    swap(from, to);
  }
  cout << from[N] << endl;
}
int main(int argc, char** argv) {
  string s;
  int i;
  if (argc == 1) ios::sync_with_stdio(false), cin.tie(0);
  for (i = 0; i < (argc - 1); i++) s += argv[i + 1], s += '\n';
  for (i = 0; i < (s.size()); i++) ungetc(s[s.size() - 1 - i], stdin);
  cout.tie(0);
  solve();
  return 0;
}