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;
template <class T>
bool mn(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool mx(T& a, const T& b) {
  return b > a ? a = b, 1 : 0;
}
template <class T>
T mxv(T& a, const T& b) {
  return b > a ? a = b : a;
}
using ll = long long;
const int MN = 2e4 + 100;
const int INF = 4e8 + 1000000;
int divf(int n, int d) {
  if (d < 0) n *= -1, d *= -1;
  if (n < 0)
    return -((-n + d - 1) / d);
  else
    return n / d;
}
bool Q;
struct Line {
 public:
  int m, b;
  mutable int r;
  Line(int m, int b) : m(m), b(b) { r = -1; }
  Line(int r) : r(r) { m = -1, b = -1; }
  int operator*(const Line& o) const {
    if (m == o.m) return o.b < b ? -INF : INF;
    return divf(o.b - b, m - o.m);
  }
  int operator[](const int& x) const { return m * x + b; }
};
struct CHT : public deque<Line> {
 public:
  void insF(Line l) {
    if (!empty() && l.m == front().m && l.b >= front().b) return;
    while (!empty() && (l.r = l * front()) >= front().r) pop_front();
    if (empty()) l.r = INF;
    push_front(l);
  }
  void insB(Line l) {
    if (!empty() && l.m == back().m && l.b >= back().b) return;
    while (!empty() && (l.r = back() * l) <= back().r) pop_back();
    if (empty()) l.r = -INF;
    push_back(l);
  }
  int qryF(int v) {
    for (; v > front().r; pop_front())
      ;
    return front()[v];
  }
  int qryB(int v) {
    for (; v <= back().r; pop_back())
      ;
    return back()[v];
  }
};
CHT cht;
void tcht(void) {
  int T;
  scanf("%d", &T);
  for (int t, a, b;;) {
    scanf("%d", &t);
    if (!~t) return;
    if (t) {
      scanf("%d%d", &a, &b);
      if (T)
        cht.insF({a, b});
      else
        cht.insB({a, b});
    } else {
      scanf("%d", &a);
      printf("%d\n", T ? cht.qryF(a) : cht.qryB(a));
    }
  }
}
int N, K;
int a[MN];
int dp[2][MN];
int v[MN];
void solve(int l, int r) {
  int *f = dp[0], *t = dp[1];
  if (r - l == 1) return;
  int m = l + (r - l >> 1);
  for (int i = m; i < r; i++) v[i] = i == m ? a[i] : max(v[i - 1], a[i]);
  for (int i = m - 1; i >= l; i--)
    v[i] = i == m - 1 ? a[i] : max(v[i + 1], a[i]);
  cht.insF({0, f[m - 1]});
  for (int i = m, j = m - 2; i < r; i++) {
    for (; j >= l && v[j + 1] <= v[i]; j--) cht.insF({m - j - 1, f[j]});
    mn(t[i], cht.qryF(v[i]) + v[i] * (i - m + 1));
  }
  cht.clear();
  for (int i = r - 1, j = l; i >= m; i--) {
    for (; j < m && v[j] >= v[i]; j++)
      cht.insB({v[j], f[j - 1] + v[j] * (m - j)});
    if (!cht.empty()) mn(t[i], cht.qryB(i - m + 1));
  }
  cht.clear();
  solve(l, m);
  solve(m, r);
}
int main(void) {
  scanf("%d%d", &N, &K);
  dp[1][0] = 0;
  for (int i = 1, m = 0; i <= N; i++)
    scanf("%d", a + i), dp[1][i] = i * mxv(m, a[i]);
  for (int i = 1; i < K; i++) {
    for (int j = 0; j <= N; j++) dp[0][j] = dp[1][j];
    solve(1, N + 1);
  }
  printf("%d\n", dp[1][N]);
  return 0;
}