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 MAXN = 20005, MAXM = 200005;
int ST_max[MAXN][16], l, r;
long long dp[MAXN][105], a[MAXN], B[MAXN], odp[MAXN];
struct Lin {
  long long k, b;
  long long val(long long x) { return k * x + b; }
  Lin(long long _k = 0, long long _b = 0) {
    k = _k;
    b = _b;
  }
} que[MAXN];
double Lin_cross_x(const Lin &A, const Lin &B) {
  return (B.b - A.b) * 1.0 / (A.k - B.k);
}
const long long INF = (long long)1e18;
struct LiChao_Segmenttree {
  long long cross_x(const Lin &A, const Lin &B) {
    return (B.b - A.b) / (A.k - B.k);
  }
  struct tree_node {
    int l, r;
    bool vis;
    bool has_lin;
    Lin lin;
  } t[4 * MAXN];
  void build(int l, int r, int root = 1) {
    t[root].l = l;
    t[root].r = r;
    t[root].vis = false;
    t[root].has_lin = false;
    if (l != r) {
      int mid = (l + r) >> 1;
      int ch = root << 1;
      build(l, mid, ch);
      build(mid + 1, r, ch + 1);
    }
  }
  void insert(Lin x, int l, int r, int root = 1) {
    t[root].vis = true;
    if (l == t[root].l && r == t[root].r) {
      if (!t[root].has_lin) {
        t[root].has_lin = true;
        t[root].lin = x;
        return;
      }
      if (t[root].lin.val(t[root].l) >= x.val(t[root].l) &&
          t[root].lin.val(t[root].r) >= x.val(t[root].r)) {
        return;
      }
      if (t[root].lin.val(t[root].l) < x.val(t[root].l) &&
          t[root].lin.val(t[root].r) < x.val(t[root].r)) {
        t[root].lin = x;
        return;
      }
      int mid = (t[root].l + t[root].r) >> 1;
      int ch = root << 1;
      if (cross_x(x, t[root].lin) <= mid) {
        if (x.k < t[root].lin.k) {
          insert(x, l, mid, ch);
        } else {
          insert(t[root].lin, l, mid, ch);
          t[root].lin = x;
        }
      } else {
        if (x.k > t[root].lin.k) {
          insert(x, mid + 1, r, ch + 1);
        } else {
          insert(t[root].lin, mid + 1, r, ch + 1);
          t[root].lin = x;
        }
      }
    } else {
      int mid = (t[root].l + t[root].r) >> 1;
      int ch = root << 1;
      if (r <= mid) {
        insert(x, l, r, ch);
      } else if (l > mid) {
        insert(x, l, r, ch + 1);
      } else {
        insert(x, l, mid, ch);
        insert(x, mid + 1, r, ch + 1);
      }
    }
    return;
  }
  void clear(int root = 1) {
    t[root].vis = false;
    t[root].has_lin = false;
    if (t[root].l != t[root].r) {
      int ch = root << 1;
      if (t[ch].vis) {
        clear(ch);
      }
      if (t[ch + 1].vis) {
        clear(ch + 1);
      }
    }
    return;
  }
  long long get_val(int x, int root = 1) {
    if (!t[root].vis) return -INF;
    long long ret;
    if (!t[root].has_lin) {
      ret = -INF;
    } else {
      ret = t[root].lin.val(x);
    }
    if (t[root].l == t[root].r) return ret;
    int ch = root << 1;
    int mid = (t[root].l + t[root].r) >> 1;
    if (x <= mid) {
      return max(ret, get_val(x, ch));
    } else {
      return max(ret, get_val(x, ch + 1));
    }
  }
} seg;
int n, k, top;
void Sparse_Table() {
  for (int i = 1; i <= n; i++) {
    ST_max[i][0] = i;
  }
  for (int j = 1; (1 << j) <= n; j++) {
    for (int i = 1; i + (1 << j) - 1 <= n; i++) {
      ST_max[i][j] = a[ST_max[i][j - 1]] > a[ST_max[i + (1 << (j - 1))][j - 1]]
                         ? ST_max[i][j - 1]
                         : ST_max[i + (1 << (j - 1))][j - 1];
    }
  }
}
int RMQ(int l, int r) {
  int k;
  for (k = 0; (1 << (k + 1)) <= r - l + 1; ++k)
    ;
  return a[ST_max[l][k]] > a[ST_max[r - (1 << k) + 1][k]]
             ? ST_max[l][k]
             : ST_max[r - (1 << k) + 1][k];
}
void q_push_front(int &head, int &tail, Lin x) {
  while (tail - head + 1 >= 2 &&
         Lin_cross_x(x, que[head]) > Lin_cross_x(x, que[head + 1]))
    ++head;
  que[--head] = x;
}
void q_push_back(int &head, int &tail, Lin x) {
  while (tail - head + 1 >= 2 &&
         Lin_cross_x(x, que[tail]) < Lin_cross_x(x, que[tail - 1]))
    --tail;
  que[++tail] = x;
}
long long q_get_val(int &head, int &tail, const int &x) {
  if (tail - head + 1 <= 0) return INF;
  while (tail - head + 1 >= 2 && que[head].val(x) > que[head + 1].val(x))
    ++head;
  return que[head].val(x);
}
pair<int, int> div_algorithm(int l, int r, int k) {
  if (l == r) {
    que[l] = Lin(-l, dp[l][k - 1]);
    dp[l][k] = -seg.get_val(l);
    return make_pair(l, r);
  }
  int pos = RMQ(l + 1, r);
  pair<int, int> LCON, RCON;
  LCON = div_algorithm(l, pos - 1, k);
  long long odp = q_get_val(LCON.first, LCON.second, a[pos]);
  seg.insert(Lin(-a[pos], -odp), pos, r);
  RCON = div_algorithm(pos, r, k);
  if (LCON.second - LCON.first <= RCON.second - RCON.first) {
    while (LCON.second >= LCON.first) {
      q_push_front(RCON.first, RCON.second, que[LCON.second--]);
    }
    return RCON;
  } else {
    while (RCON.second >= RCON.first) {
      q_push_back(LCON.first, LCON.second, que[RCON.first++]);
    }
    return LCON;
  }
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; ++i) {
    scanf("%lld", &a[i]);
  }
  seg.build(1, 20000);
  Sparse_Table();
  for (int i = 1; i <= n; ++i) {
    dp[i][1] = a[RMQ(1, i)] * i;
  }
  for (int i = 2; i <= k; ++i) {
    for (int j = 1; j <= n; ++j) {
      dp[j][i] = INF;
    }
    seg.clear();
    div_algorithm(i - 1, n, i);
  }
  printf("%lld\n", dp[n][k]);
  return 0;
}