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;
namespace Dango {
const int MAXN = 20005, MAXK = 105;
const long long INF = 0x3f3f3f3f3f3f3f3f;
struct tree {
  int l, r, lt, rt;
  long long k, b;
  bool flag;
} t[MAXN * 40];
int n, k, num[MAXN];
int st[MAXN], top;
int now;
int root[MAXN], cnt;
long long dp[MAXK][MAXN];
struct hull {
  deque<int> point;
  void merge(hull &b) {
    if (b.point.size() > point.size()) {
      int s = b.point.size() - 1;
      for (int i = 0; i < point.size(); i++) {
        int x = point[i];
        while (s && (dp[now][b.point[s] - 1] - dp[now][b.point[s - 1] - 1]) *
                                (x - b.point[s]) -
                            (dp[now][x - 1] - dp[now][b.point[s] - 1]) *
                                (b.point[s] - b.point[s - 1]) >=
                        0) {
          b.point.pop_back();
          s--;
        }
        b.point.push_back(x);
        s++;
      }
      point.swap(b.point);
    } else {
      for (int i = b.point.size() - 1; i >= 0; i--) {
        int x = b.point[i];
        while (point.size() > 1 &&
               (dp[now][point[0] - 1] - dp[now][point[1] - 1]) *
                           (x - point[0]) -
                       (dp[now][x - 1] - dp[now][point[0] - 1]) *
                           (point[0] - point[1]) <=
                   0)
          point.pop_front();
        point.push_front(x);
      }
    }
    b.point.clear();
  }
  long long query(long long k) {
    int l = 1, r = point.size() - 1;
    int pos = point[0];
    while (l <= r) {
      int mid = (l + r) >> 1;
      if (dp[now][point[mid] - 1] - dp[now][point[mid - 1] - 1] <=
          k * (point[mid] - point[mid - 1])) {
        pos = point[mid];
        l = mid + 1;
      } else
        r = mid - 1;
    }
    return dp[now][pos - 1] - k * (pos - 1);
  }
} h[MAXN];
int read() {
  int x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) {
    f |= (ch == '-');
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f ? -x : x;
}
void init_for_one() {
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    mx = max(mx, num[i]);
    dp[1][i] = 1ll * mx * i;
  }
  t[0].l = 1;
  t[0].r = n;
}
void update(int a, long long k, long long b) {
  if (!t[a].flag) {
    t[a].flag = true;
    t[a].k = k;
    t[a].b = b;
    return;
  }
  int mid = (t[a].l + t[a].r) >> 1;
  long long kk = t[a].k, bb = t[a].b;
  long long ly0 = kk * t[a].l + bb, ry0 = kk * t[a].r + bb;
  long long ly1 = k * t[a].l + b, ry1 = k * t[a].r + b;
  if (ly1 <= ly0 && ry1 <= ry0) {
    t[a].k = k;
    t[a].b = b;
  } else if (ly1 >= ly0 && ry1 >= ry0)
    ;
  else {
    t[++cnt] = t[t[a].lt];
    t[cnt].l = t[a].l;
    t[cnt].r = mid;
    t[a].lt = cnt;
    t[++cnt] = t[t[a].rt];
    t[cnt].l = mid + 1;
    t[cnt].r = t[a].r;
    t[a].rt = cnt;
    if (k * mid + b > kk * mid + bb) {
      if (ly1 >= ly0) {
        update(t[a].rt, k, b);
      } else
        update(t[a].lt, k, b);
    } else {
      t[a].k = k;
      t[a].b = b;
      if (ly1 >= ly0) {
        update(t[a].lt, kk, bb);
      } else
        update(t[a].rt, kk, bb);
    }
  }
}
long long query(int a, int x) {
  long long res = t[a].flag ? t[a].k * x + t[a].b : INF;
  if (a && t[a].l != t[a].r) {
    int mid = (t[a].l + t[a].r) >> 1;
    res = min(res, x <= mid ? query(t[a].lt, x) : query(t[a].rt, x));
  }
  return res;
}
void init() {
  top = 0;
  cnt = 0;
  for (int i = 1; i <= n; i++) {
    h[i].point.clear();
    h[i].point.push_back(i);
  }
}
int work() {
  n = read();
  k = read();
  for (int i = 1; i <= n; i++) num[i] = read();
  init_for_one();
  for (int i = 2; i <= k; i++) {
    now = i - 1;
    init();
    for (int j = i; j <= n; j++) {
      while (top && num[st[top]] < num[j]) {
        h[j].merge(h[st[top]]);
        top--;
      }
      root[j] = ++cnt;
      t[root[j]] = t[root[st[top]]];
      st[++top] = j;
      update(root[j], num[j], h[j].query(num[j]));
      dp[now + 1][j] = query(root[j], j);
    }
  }
  printf("%lld", dp[k][n]);
  return 0;
}
}  // namespace Dango
int main() { return Dango::work(); }