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;
using ll = long long;
const int N = 2e5 + 5;
int n, k;
int a[N];
int lg[N], rmq[N][20];
ll dp[N][2];
int getMax(int l, int r) {
  int k = lg[r - l + 1];
  return max(rmq[l][k], rmq[r - (1 << k) + 1][k]);
}
struct line {
  ll a, b;
  line(ll _a = 0, ll _b = 0) {
    a = _a;
    b = _b;
  }
  ll f(ll x) { return a * x + b; }
};
struct CHT {
  vector<line> s;
  void reset() { s.clear(); }
  bool bad(line l1, line l2, line l3) {
    return (double)(l3.b - l1.b) / (double)(l1.a - l3.a) <=
           (double)(l2.b - l1.b) / (double)(l1.a - l2.a);
  }
  void add(line l) {
    while (s.size() > 0 && s.back().a == l.a && s.back().b >= l.b) {
      s.pop_back();
    }
    if (s.size() > 0 && s.back().a == l.a && s.back().b < l.b) {
      return;
    }
    while (s.size() > 1 && bad(s[s.size() - 2], s.back(), l)) {
      s.pop_back();
    }
    s.push_back(l);
  }
  ll get(ll x) {
    if (s.size() == 0) return 1e9;
    int L = 0, R = s.size() - 1;
    while (L < R) {
      int mid = (L + R) >> 1;
      if (s[mid].f(x) >= s[mid + 1].f(x)) {
        L = mid + 1;
      } else {
        R = mid;
      }
    }
    return s[L].f(x);
  }
} cht;
void solve(int l, int r) {
  int mid = (l + r) >> 1;
  cht.reset();
  int ptr = mid + 1;
  for (int i = mid; i <= r; i++) {
    while (ptr - 1 >= l && getMax(ptr - 1, mid) <= getMax(mid, i)) {
      ptr--;
      cht.add(line(ptr, dp[ptr - 1][0]));
    }
    dp[i][1] = min(dp[i][1],
                   cht.get(-getMax(mid, i)) + 1LL * (i + 1) * getMax(mid, i));
  }
  cht.reset();
  ptr = l - 1;
  for (int i = r; i >= mid; i--) {
    while (ptr + 1 <= mid && getMax(ptr + 1, mid) > getMax(mid, i)) {
      ptr++;
      cht.add(line(getMax(ptr, mid),
                   dp[ptr - 1][0] + 1LL * (-ptr + 1) * getMax(ptr, mid)));
    }
    dp[i][1] = min(dp[i][1], cht.get(i));
  }
  if (l == r) return;
  solve(l, mid);
  solve(mid + 1, r);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    lg[i] = log2(i);
    rmq[i][0] = a[i];
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      rmq[i][j] = max(rmq[i][j - 1], rmq[i + (1 << (j - 1))][j - 1]);
    }
  }
  for (int i = 0; i <= n; i++) {
    dp[i][0] = dp[i][1] = 1e9;
  }
  dp[0][1] = 0;
  for (int i = 1; i <= k; i++) {
    for (int j = 0; j <= n; j++) {
      dp[j][0] = dp[j][1];
      dp[j][1] = 1e9;
    }
    solve(1, n);
  }
  cout << dp[n][1];
}