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;
long long INF = (long long)1e18;
long double inter(pair<long long, long long> L1,
                  pair<long long, long long> L2) {
  return 1.0 * (L2.second - L1.second) / (L1.first - L2.first);
}
struct Convex {
  vector<pair<long long, long long> > mas;
  int uk = -1;
  void add(pair<long long, long long> L) {
    while ((int)mas.size() > 1) {
      pair<long long, long long> L1 = mas.back();
      mas.pop_back();
      pair<long long, long long> L2 = mas.back();
      if (inter(L2, L1) < inter(L1, L)) {
        mas.push_back(L1);
        break;
      }
    }
    mas.push_back(L);
    if (uk >= (int)mas.size()) uk = (int)mas.size() - 1;
    if (uk == -1) uk = 0;
    return;
  }
  void clear() {
    mas.clear();
    return;
  }
  long long get_min(long long first) {
    while (uk < (int)mas.size() - 1) {
      long double x0 = inter(mas[uk], mas[uk + 1]);
      if (x0 > first) break;
      uk++;
    }
    return mas[uk].first * first + mas[uk].second;
  }
};
int first = 0, dv[18][20005];
long long a[20005], dp[5][20005];
vector<pair<long long, int> > spis;
pair<long long, long long> line[20005];
Convex tree[80005];
void build(int v, int lef, int rig) {
  if (lef == rig) {
    tree[v].clear();
    tree[v].add(make_pair(-lef, dp[first ^ 1][lef - 1]));
    return;
  }
  int mid = (lef + rig) / 2;
  build(2 * v, lef, mid);
  build(2 * v + 1, mid + 1, rig);
  tree[v] = tree[2 * v];
  for (int i = 0; i < (int)tree[2 * v + 1].mas.size(); i++)
    tree[v].add(tree[2 * v + 1].mas[i]);
  return;
}
long long get_min(int v, int lef, int rig, int A, int B, long long first) {
  if (lef > B || rig < A) return INF;
  if (A <= lef && rig <= B) return tree[v].get_min(first);
  int mid = (lef + rig) / 2;
  return min(get_min(2 * v, lef, mid, A, B, first),
             get_min(2 * v + 1, mid + 1, rig, A, B, first));
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, k, H = 0;
  cin >> n >> k;
  while ((1 << H) <= n) H++;
  for (int i = 1; i <= n; i++) cin >> a[i];
  long long mx = a[1];
  for (int i = 1; i <= n; i++) {
    mx = max(mx, a[i]);
    dp[0][i] = (long long)i * mx;
  }
  for (int rep = 2; rep <= k; rep++) {
    first ^= 1;
    build(1, 1, n);
    spis.clear();
    for (int i = 1; i <= n; i++) {
      while (!spis.empty() && spis.back().first <= a[i]) spis.pop_back();
      int lef = 1;
      if (!spis.empty()) lef = spis.back().second + 1;
      spis.push_back(make_pair(a[i], i));
      long long value = get_min(1, 1, n, lef, i, a[i]);
      line[i] = make_pair(a[i], value);
      int pos = lef - 1;
      for (int j = H; j >= 0; j--) {
        int tek = dv[j][pos];
        if (tek == 0 || dv[0][tek] == 0) continue;
        if (inter(line[dv[0][tek]], line[tek]) >= inter(line[tek], line[i]))
          pos = dv[0][tek];
      }
      if (dv[0][pos] != 0 &&
          inter(line[dv[0][pos]], line[pos]) >= inter(line[pos], line[i]))
        pos = dv[0][pos];
      dv[0][i] = pos;
      for (int j = 1; j <= H; j++)
        if (dv[j - 1][i] != 0)
          dv[j][i] = dv[j - 1][dv[j - 1][i]];
        else
          dv[j][i] = 0;
      pos = i;
      for (int j = H; j >= 0; j--) {
        int tek = dv[j][pos];
        if (tek == 0 || dv[0][tek] == 0) continue;
        if (inter(line[dv[0][tek]], line[tek]) >= i + 1) pos = dv[0][tek];
      }
      if (dv[0][pos] != 0 && inter(line[dv[0][pos]], line[pos]) >= i + 1)
        pos = dv[0][pos];
      dp[first][i] = line[pos].first * (long long)(i + 1) + line[pos].second;
    }
  }
  cout << dp[first][n];
  return 0;
}