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 N = 2e4 + 5, MAXK = 105, inf = (long long)1e9 + 123;
long long n, K, a[N], dp[N][MAXK], pref[N], suff[N], pter, mx[N];
struct ConvexHull {
  vector<long long> A, B;
  void reset() {
    A.clear();
    B.clear();
  }
  bool bad(bool _, long long l1, long long l2, long long l3) {
    if (_)
      return (B[l2] - B[l1]) * (A[l1] - A[l3]) >=
             (B[l3] - B[l1]) * (A[l1] - A[l2]);
    else
      return (B[l2] - B[l1]) * (A[l1] - A[l3]) <=
             (B[l3] - B[l1]) * (A[l1] - A[l2]);
  }
  void add(bool _, long long _A, long long _B) {
    while (A.size() && _A == A.back() && _B <= B.back())
      A.pop_back(), B.pop_back();
    A.push_back(_A);
    B.push_back(_B);
    while (A.size() > 2 &&
           bad(_, (long long)A.size() - 3, (long long)A.size() - 2,
               (long long)A.size() - 1))
      A.erase(A.end() - 2), B.erase(B.end() - 2);
  }
  long long f(long long x, long long _) { return A[_] * x + B[_]; }
  long long get(long long x) {
    if (!A.size()) return inf;
    long long l = 0, r = (long long)A.size() - 1;
    while (r - l > 6) {
      long long mid = (l + r) >> 1;
      if (f(x, mid) < f(x, mid + 1))
        r = mid;
      else if (f(x, mid) > f(x, mid + 1))
        l = mid + 1;
      else {
        if (f(x, mid - 1) < f(x, mid))
          r = mid;
        else
          l = mid + 1;
      }
    }
    long long ret = inf;
    for (long long i = l; i <= r; ++i) ret = min(ret, f(x, i));
    return ret;
  }
} ch;
void solve(long long _, long long l, long long r) {
  if (l == r) return;
  long long mid = (l + r) >> 1;
  solve(_, l, mid);
  solve(_, mid + 1, r);
  pref[mid + 1] = a[mid + 1];
  for (long long i = mid + 2; i <= r; ++i) pref[i] = max(pref[i - 1], a[i]);
  suff[mid] = a[mid];
  for (long long i = mid - 1; i >= l; --i) suff[i] = max(suff[i + 1], a[i]);
  for (long long j = _; j <= _; ++j) {
    ch.reset();
    pter = l;
    for (long long i = r; i > mid; --i) {
      while (pter < mid && suff[pter + 1] >= pref[i]) {
        if (dp[pter][j - 1] != inf)
          ch.add(1, suff[pter + 1], -pter * suff[pter + 1] + dp[pter][j - 1]);
        ++pter;
      }
      dp[i][j] = min(dp[i][j], ch.get(i));
    }
  }
  for (long long j = _; j <= _; ++j) {
    ch.reset();
    pter = mid;
    for (long long i = mid + 1; i <= r; ++i) {
      while (pter >= l && (pter == mid || suff[pter + 1] <= pref[i])) {
        if (dp[pter][j - 1] != inf) ch.add(0, -pter, dp[pter][j - 1]);
        --pter;
      }
      dp[i][j] = min(dp[i][j], ch.get(pref[i]) + i * pref[i]);
    }
  }
}
int32_t main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> K;
  for (long long i = 1; i <= n; ++i) cin >> a[i], mx[i] = max(mx[i - 1], a[i]);
  for (long long i = 1; i <= n; ++i) dp[i][1] = i * mx[i];
  for (long long i = 2; i <= K; ++i) {
    for (long long j = 1; j <= n; ++j) dp[j][i] = inf;
    solve(i, 1, n);
  }
  cout << dp[n][K];
  return 0;
}