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 int N = int(2e4) + 10, K = 112;
const long long inf = (long long)(1e18) + 10;
long long dp[N][K];
int n, k, a[N];
int sz[4 * N][2], lnk[4 * N][2], l[N], r[N];
vector<pair<long long, long long> > line[4 * N][2];
void add(int id, int v, pair<long long, long long> p) {
  int k = sz[v][id];
  while (k > 0) {
    if ((p.second - line[v][id][k].second) *
            (line[v][id][k - 1].first - line[v][id][k].first) >
        (line[v][id][k].first - p.first) *
            (line[v][id][k].second - line[v][id][k - 1].second))
      break;
    k--;
    line[v][id].pop_back();
  }
  line[v][id].push_back(p);
  k++;
  sz[v][id] = k;
}
long long get(int id, int v, long long x) {
  if (sz[v][id] == -1) return inf;
  int k = min(lnk[v][id], sz[v][id]);
  while (k < sz[v][id]) {
    if ((line[v][id][k + 1].second - line[v][id][k].second) >=
        x * (line[v][id][k].first - line[v][id][k + 1].first))
      break;
    k++;
  }
  lnk[v][id] = max(0, k - 1);
  return line[v][id][k].first * x + line[v][id][k].second;
}
void calc() {
  stack<int> st;
  for (int i = 1; i <= n; i++) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    if (st.empty())
      l[i] = 1;
    else
      l[i] = st.top() + 1;
    st.push(i);
  }
  while (!st.empty()) st.pop();
  for (int i = n; i > 0; i--) {
    while (!st.empty() && a[st.top()] <= a[i]) st.pop();
    if (st.empty())
      r[i] = n;
    else
      r[i] = st.top() - 1;
    st.push(i);
  }
}
void clear(int id, int v, int tl, int tr) {
  line[v][id].clear();
  if (tl == tr) return;
  int tm = (tl + tr) >> 1;
  clear(id, v + v, tl, tm);
  clear(id, v + v + 1, tm + 1, tr);
}
void upd0(int id, int v, int tl, int tr, int pos,
          pair<long long, long long> p) {
  add(id, v, p);
  if (tl == tr) return;
  int tm = (tl + tr) >> 1;
  if (pos <= tm)
    upd0(id, v + v, tl, tm, pos, p);
  else
    upd0(id, v + v + 1, tm + 1, tr, pos, p);
}
long long get0(int id, int v, int tl, int tr, int l, int r, long long x) {
  if (tl > r || l > tr) return inf;
  if (l <= tl && tr <= r) {
    return get(id, v, x);
  }
  int tm = (tl + tr) >> 1;
  return min(get0(id, v + v, tl, tm, l, r, x),
             get0(id, v + v + 1, tm + 1, tr, l, r, x));
}
void upd1(int id, int v, int tl, int tr, int l, int r,
          pair<long long, long long> p) {
  if (tl > r || l > tr) return;
  if (l <= tl && tr <= r) {
    add(id, v, p);
    return;
  }
  int tm = (tl + tr) >> 1;
  upd1(id, v + v, tl, tm, l, r, p);
  upd1(id, v + v + 1, tm + 1, tr, l, r, p);
}
long long res;
void get1(int id, int v, int tl, int tr, int pos, long long x) {
  res = min(res, get(id, v, x));
  if (tl == tr) return;
  int tm = (tl + tr) >> 1;
  if (pos <= tm)
    get1(id, v + v, tl, tm, pos, x);
  else
    get1(id, v + v + 1, tm + 1, tr, pos, x);
}
int main() {
  scanf("%d%d", &n, &k);
  long long sum = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    sum += a[i];
  }
  calc();
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[i]);
    dp[i][1] = 1ll * mx * i;
  }
  for (int kk = 2; kk <= k; kk++) {
    clear(0, 1, 1, n);
    clear(1, 1, 1, n);
    memset(sz, -1, sizeof(sz));
    memset(lnk, 0, sizeof(lnk));
    for (int i = 1; i <= n; i++) {
      if (dp[i][kk - 1] != inf)
        upd0(0, 1, 1, n, i, make_pair(-i, dp[i][kk - 1]));
      long long mn = get0(0, 1, 1, n, max(l[i] - 1, 1), i, a[i]);
      upd1(1, 1, 1, n, i, r[i], make_pair(a[i], mn));
      res = inf;
      get1(1, 1, 1, n, i, i);
      dp[i][kk] = res;
    }
  }
  printf("%lld\n", dp[n][k]);
  return 0;
}