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>
const int N = 20054, INF = 0x3f3f3f3f;
struct vec2 {
  int x, y;
  vec2(int x0 = 0, int y0 = 0) : x(x0), y(y0) {}
  inline vec2 operator-(const vec2 &B) const { return vec2(x - B.x, y - B.y); }
  inline long long operator*(const vec2 &B) const {
    return (long long)x * B.x + (long long)y * B.y;
  }
  inline long long operator^(const vec2 &B) const {
    return (long long)x * B.y - (long long)y * B.x;
  }
  inline long long norm2() const { return (long long)x * x + (long long)y * y; }
};
int n, K;
int a[N], pp[N], po[N];
int dp[2][N], *cur = *dp, *nxt = dp[1];
inline void up(int &x, const int y) { x < y ? x = y : 0; }
inline void down(int &x, const int y) { x > y ? x = y : 0; }
namespace hull {
vec2 ch[N], *tail;
inline void reset() { tail = ch; }
void insert(const vec2 &P) {
  if (tail != ch && tail[-1].x == P.x && tail[-1].y <= P.y) return;
  for (; tail > ch + 1 && (((P) - (tail[-2])) ^ ((tail[-1]) - (tail[-2]))) <= 0;
       --tail)
    ;
  *tail++ = P;
}
int query(const vec2 &P) {
  if (ch == tail) return INF;
  int L = 0, R = tail - ch - 1, M;
  for (; L<R; M = (L + R) / 2, ch[M] * P> ch[M + 1] *P ? L = M + 1 : R = M)
    ;
  return (int)std::min<long long>(ch[L] * P, INF);
}
}  // namespace hull
void solve(int L, int R) {
  if (L + 1 == R) return;
  int i, j, M = (L + R) / 2, lm, rm;
  j = M, lm = rm = 0, hull::reset();
  for (i = M; i < R; ++i) {
    for (up(rm, a[i]); j > L && lm <= a[i];)
      if (up(lm, a[--j]), cur[j] < INF) hull::insert(vec2(j, cur[j]));
    down(nxt[i], hull::query(vec2(-rm, 1)) + i * rm), pp[i] = j;
  }
  for (po[j = M - 1] = a[M]; j > L; --j) up(po[j - 1] = po[j], a[j]);
  j = L, lm = rm = 0, hull::reset();
  for (i = R - 1; i >= M; --i) {
    for (; j < pp[i]; ++j)
      if (cur[j] < INF) hull::insert(vec2(po[j], cur[j] - j * po[j]));
    down(nxt[i], hull::query(vec2(i, 1)));
  }
  solve(L, M), solve(M, R);
}
int main() {
  int i;
  scanf("%d%d", &n, &K);
  for (i = 0; i < n; ++i) scanf("%d", a + i);
  for (*nxt = *a, i = 1; i < n; ++i) up(nxt[i] = nxt[i - 1], a[i]);
  for (i = 0; i < n; ++i) nxt[i] *= i + 1;
  for (; --K; std::swap(cur, nxt), memset(nxt, 63, n << 2), solve(0, n))
    ;
  printf("%d\n", nxt[n - 1]);
  return 0;
}