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;
const long long NMAX = 250005;
const long long INF = (1LLU << 62) - 1;
int v[NMAX];
int stk[NMAX];
vector<pair<long long, long long> > aint[4 * NMAX];
bool check(pair<long long, long long> a, pair<long long, long long> b,
           pair<long long, long long> c) {
  return (1. * (a.second - c.second) / (c.first - a.first) <=
          1. * (a.second - b.second) / (b.first - a.first));
}
void add(int node, long long j, long long x) {
  while (aint[node].size() >= 2 &&
         check(aint[node][aint[node].size() - 2],
               aint[node][aint[node].size() - 1], {j, x}))
    aint[node].pop_back();
  aint[node].push_back({j, x});
}
void update(int node, int l, int r, long long j, long long x) {
  add(node, -j, x);
  if (l == r) return;
  int med = (l + r) / 2;
  if (med >= j)
    update(2 * node, l, med, j, x);
  else
    update(2 * node + 1, med + 1, r, j, x);
}
void rev(int node, int l, int r) {
  reverse(aint[node].begin(), aint[node].end());
  if (l == r) return;
  int med = (l + r) / 2;
  rev(2 * node, l, med);
  rev(2 * node + 1, med + 1, r);
}
long long eval(pair<long long, long long> d, long long x) {
  return d.first * x + d.second;
}
long long getVal(int node, long long x) {
  while (aint[node].size() >= 2 &&
         eval(aint[node][aint[node].size() - 2], x) <=
             eval(aint[node][aint[node].size() - 1], x))
    aint[node].pop_back();
  return eval(aint[node].back(), x);
}
long long query(int node, int l, int r, int x, int y, long long w) {
  if (x <= l && r <= y) return getVal(node, w);
  int med = (l + r) / 2;
  long long ans = INF;
  if (x <= med) ans = min(ans, query(2 * node, l, med, x, y, w));
  if (y > med) ans = min(ans, query(2 * node + 1, med + 1, r, x, y, w));
  return ans;
}
void clr(int node, int l, int r) {
  aint[node].clear();
  if (l == r) return;
  int med = (l + r) / 2;
  clr(2 * node, l, med);
  clr(2 * node + 1, med + 1, r);
}
pair<long long, long long> f[NMAX];
struct Lines {
  int stk[NMAX];
  pair<int, int> upd[NMAX];
  int top, updc;
  Lines() { top = updc = 0; }
  void add(int i) {
    int pos = top + 1;
    if (top == 0)
      pos = 1;
    else if (f[stk[1]].first >= f[i].first && f[stk[1]].second >= f[i].second)
      pos = 1;
    else {
      int l = 2, r = top;
      while (l <= r) {
        int med = (l + r) / 2;
        if (check(f[stk[med - 1]], f[stk[med]], f[i])) {
          r = med - 1;
          pos = med;
        } else {
          l = med + 1;
        }
      }
    }
    upd[++updc] = {top, stk[pos]};
    stk[pos] = i;
    top = pos;
  }
  long long eval(long long x) {
    int l = 1, r = top;
    while (r - l >= 3) {
      int m1 = l + (r - l) / 3;
      int m2 = r - (r - l) / 3;
      if (f[stk[m1]].first * x + f[stk[m1]].second <
          f[stk[m2]].first * x + f[stk[m2]].second)
        r = m2;
      else
        l = m1;
    }
    long long ans = INF;
    for (; l <= r; ++l) ans = min(ans, f[stk[l]].first * x + f[stk[l]].second);
    return ans;
  }
  void undo() {
    stk[top] = upd[updc].second;
    top = upd[updc].first;
    updc--;
  }
  void clr() { top = updc = 0; }
};
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  long long **dp = new long long *[k + 5];
  for (int i = 0; i <= k; ++i) dp[i] = new long long[n + 5];
  for (int i = 1; i <= k; ++i)
    for (int j = 0; j <= n; ++j) dp[i][j] = INF;
  dp[1][0] = 0;
  int m = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &v[i]);
    m = max(m, v[i]);
    dp[1][i] = 1LL * i * m;
  }
  Lines b;
  for (int j = 2; j <= k; ++j) {
    for (int i = 1; i <= n; ++i) update(1, 1, n, i, dp[j - 1][i - 1]);
    rev(1, 1, n);
    int top = 0;
    for (int i = 1; i <= n; ++i) {
      while (top && v[stk[top]] <= v[i]) {
        top--;
        b.undo();
      }
      stk[++top] = i;
      f[i] = {v[i], query(1, 1, n, stk[top - 1] + 1, i, v[i])};
      b.add(i);
      dp[j][i] = b.eval(i + 1);
    }
    b.clr();
    clr(1, 1, n);
  }
  printf("%lld\n", dp[k][n]);
  return 0;
}