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;
template <class T>
using v2d = vector<vector<T>>;
template <class T>
bool uin(T &a, T b) {
  return a > b ? (a = b, true) : false;
}
template <class T>
bool uax(T &a, T b) {
  return a < b ? (a = b, true) : false;
}
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
const int maxN = 2e4 + 10;
const int maxK = 1e2 + 10;
const int inf = 1e9;
int n, k, h[maxN], a[maxN], f[maxN], g[maxN], c[maxN];
vector<int> sorted, adj[maxN];
stack<int> st;
bool flag[maxN];
struct Line {
  int a, b;
  Line(int a, int b) : a(a), b(b) {}
  bool good(Line &e, Line &f) {
    return (long long)(b - e.b) * (f.a - e.a) >
           (long long)(e.b - f.b) * (e.a - a);
  }
  int valueAt(int x) { return a * x + b; }
};
struct PCHT : vector<Line> {
  stack<pair<Line, bool>> s;
  void addLine(Line d) {
    while ((int)size() >= 2 && !d.good(back(), (*this)[(int)size() - 2])) {
      s.emplace(back(), 1);
      pop_back();
    }
    s.emplace(d, 0);
    push_back(d);
  }
  void rollback() {
    do {
      if (s.top().second) {
        push_back(s.top().first);
      } else {
        pop_back();
      }
      s.pop();
    } while (!s.empty() && s.top().second);
  }
  int query(int x) {
    int l = 0, r = (int)size();
    while (r - l > 1) {
      int mid = (l + r) / 2;
      if ((*this)[mid].valueAt(x) <= (*this)[mid - 1].valueAt(x)) {
        l = mid;
      } else {
        r = mid;
      }
    }
    return (*this)[l].valueAt(x);
  }
};
struct CHT : vector<Line> {
  int id = 0;
  void addLine(Line d) {
    while ((int)size() - id >= 2 && !d.good(back(), (*this)[(int)size() - 2])) {
      pop_back();
    }
    push_back(d);
  }
  int query(int x) {
    while ((int)size() - id >= 2 &&
           (*this)[id].valueAt(x) >= (*this)[id + 1].valueAt(x)) {
      id++;
    }
    return (*this)[id].valueAt(x);
  }
};
CHT b[maxN * 4];
PCHT cur;
int L, R, val;
void build(int x, int lo, int hi) {
  if (lo == hi) {
    b[x].clear();
    b[x].emplace_back(-lo, f[lo]);
    return;
  }
  int mid = (lo + hi) / 2;
  build(x * 2, lo, mid);
  build(x * 2 + 1, mid + 1, hi);
  b[x] = b[x * 2];
  for (auto &d : b[x * 2 + 1]) {
    b[x].addLine(d);
  }
}
int query(int x, int lo, int hi) {
  if (lo > R || hi < L) {
    return inf;
  }
  if (lo >= L && hi <= R) {
    return b[x].query(val);
  }
  int mid = (lo + hi) / 2;
  return min(query(x * 2, lo, mid), query(x * 2 + 1, mid + 1, hi));
}
void dfs(int u) {
  flag[u] = 1;
  cur.addLine(Line(a[u], c[u]));
  g[u] = cur.query(u);
  for (auto &v : adj[u]) {
    if (!flag[v]) {
      dfs(v);
    }
  }
  cur.rollback();
}
void solve() {
  cin >> n >> k;
  for (int i = 1; i <= (int)(n); ++i) {
    cin >> a[i];
  }
  f[0] = inf;
  int mx = -inf;
  for (int i = 1; i <= (int)(n); ++i) {
    uax(mx, a[i]);
    f[i] = i * mx;
  }
  sorted.resize(n);
  iota((sorted).begin(), (sorted).end(), 1);
  sort((sorted).begin(), (sorted).end(),
       [](int i, int j) { return a[i] < a[j]; });
  for (int i = 1; i <= (int)(n); ++i) {
    while (!st.empty() && a[st.top()] <= a[i]) {
      st.pop();
    }
    if (!st.empty()) {
      h[i] = st.top();
      adj[st.top()].emplace_back(i);
    }
    st.push(i);
  }
  for (int t = (int)(2); t <= (int)(k); ++t) {
    build(1, 0, n - 1);
    for (auto &i : sorted) {
      L = h[i], R = i - 1, val = a[i];
      c[i] = query(1, 0, n - 1);
    }
    fill(flag + 1, flag + n + 1, 0);
    for (int i = 1; i <= (int)(n); ++i) {
      if (!flag[i]) {
        cur = PCHT();
        dfs(i);
      }
    }
    copy(g + 1, g + n + 1, f + 1);
  }
  cout << f[n];
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int T = 1;
  while (T--) {
    solve();
  }
  return 0;
}