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 Nmax = 1e5 + 5;
const long long inf = 1e18;
int n, k, nr, st[Nmax], A[Nmax], nextBigger[Nmax];
long long dp[Nmax], old[Nmax];
struct Ec {
  int a;
  long long b;
  long long operator()(int x) { return (long long)a * x + b; }
};
Ec interv[Nmax];
class Batch {
  vector<Ec> v;
  double intersect(Ec A, Ec B) { return (double)(A.b - B.b) / (B.a - A.a); }
  bool bad(Ec a, Ec b, Ec c) { return intersect(a, c) >= intersect(a, b); }

 public:
  void clear() { v.clear(); }
  void add(Ec ec) {
    while (v.size() >= 2 && bad(v[v.size() - 2], v.back(), ec)) v.pop_back();
    v.push_back(ec);
  }
  long long query(int x) {
    if (v.empty()) return inf;
    while (v.size() >= 2 && intersect(v[v.size() - 2], v.back()) <= x)
      v.pop_back();
    return v.back()(x);
  }
};
class SegmentTree {
  Batch a[Nmax << 2];

 public:
  void update1(int node, int st, int dr, int pos, Ec ec) {
    a[node].add(ec);
    if (st == dr) return;
    if (pos <= ((st + dr) >> 1))
      update1((node << 1), st, ((st + dr) >> 1), pos, ec);
    else
      update1(((node << 1) | 1), ((st + dr) >> 1) + 1, dr, pos, ec);
  }
  void update2(int node, int st, int dr, int L, int R, Ec ec) {
    if (L <= st && dr <= R) {
      a[node].add(ec);
      return;
    }
    if (L <= ((st + dr) >> 1))
      update2((node << 1), st, ((st + dr) >> 1), L, R, ec);
    if (((st + dr) >> 1) < R)
      update2(((node << 1) | 1), ((st + dr) >> 1) + 1, dr, L, R, ec);
  }
  long long query1(int node, int st, int dr, int L, int R, int p) {
    if (L <= st && dr <= R) return a[node].query(p);
    long long x = inf, y = inf;
    if (L <= ((st + dr) >> 1))
      x = query1((node << 1), st, ((st + dr) >> 1), L, R, p);
    if (((st + dr) >> 1) < R)
      y = query1(((node << 1) | 1), ((st + dr) >> 1) + 1, dr, L, R, p);
    return min(x, y);
  }
  long long query2(int node, int st, int dr, int pos, int p) {
    long long x = a[node].query(p);
    if (st == dr) return x;
    if (pos <= ((st + dr) >> 1))
      x = min(x, query2((node << 1), st, ((st + dr) >> 1), pos, p));
    else
      x = min(x, query2(((node << 1) | 1), ((st + dr) >> 1) + 1, dr, pos, p));
    return x;
  }
  void clear() {
    int i;
    for (i = 1; i <= ((n + 1) << 2); ++i) a[i].clear();
  }
} aint;
void solve() {
  int i;
  aint.clear();
  for (i = n; i >= 0; --i) aint.update1(1, 0, n, i, {-i, old[i]});
  nr = 0;
  st[0] = 0;
  for (i = 1; i <= n; ++i) {
    while (nr && A[i] >= A[st[nr]]) --nr;
    st[++nr] = i;
    interv[i] = {A[i], aint.query1(1, 0, n, st[nr - 1], st[nr] - 1, A[i])};
  }
  aint.clear();
  for (i = n; i >= 1; --i)
    aint.update2(1, 0, n, i, nextBigger[i] - 1, interv[i]);
  for (i = 1; i <= n; ++i) dp[i] = aint.query2(1, 0, n, i, i);
}
int main() {
  int i, j;
  cin >> n >> k;
  for (i = 1; i <= n; ++i) cin >> A[i];
  nr = 0;
  st[0] = n + 1;
  for (i = n; i; --i) {
    while (nr && A[i] > A[st[nr]]) --nr;
    nextBigger[i] = st[nr];
    st[++nr] = i;
  }
  old[0] = 0;
  for (i = 1; i <= n; ++i) old[i] = inf;
  for (i = 1; i <= k; ++i) {
    for (j = 1; j <= n; ++j) dp[j] = inf;
    dp[0] = 0;
    solve();
    for (j = 1; j <= n; ++j) old[j] = dp[j];
  }
  cout << dp[n] << '\n';
  return 0;
}