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;
double get_sect(pair<long long, long long> a, pair<long long, long long> b) {
  return ((double)b.second - a.second) / (a.first - b.first);
}
class LinearMinConvexHull {
 public:
  deque<double> sect;
  deque<pair<long long, long long> > lines;
  bool bad_back(pair<long long, long long> line) {
    if ((int)lines.size() <= 1) {
      return false;
    }
    if (sect.back() >= get_sect(lines[(int)lines.size() - 2], line)) {
      return true;
    }
    return false;
  }
  bool bad_front(pair<long long, long long> line) {
    if ((int)lines.size() <= 1) {
      return false;
    }
    if (sect.front() <= get_sect(lines[1], line)) {
      return true;
    }
    return false;
  }
  void del_back_line() {
    lines.pop_back();
    if (sect.size()) {
      sect.pop_back();
    }
  }
  void del_front_line() {
    lines.pop_front();
    if (sect.size()) {
      sect.pop_front();
    }
  }
  void ins_back_line(pair<long long, long long> line) {
    lines.push_back(line);
    if ((int)lines.size() >= 2) {
      sect.push_back(
          get_sect(lines[(int)lines.size() - 2], lines[(int)lines.size() - 1]));
    }
  }
  void ins_front_line(pair<long long, long long> line) {
    lines.push_front(line);
    if ((int)lines.size() >= 2) {
      sect.push_front(get_sect(lines[0], lines[1]));
    }
  }

 public:
  void add_back(pair<long long, long long> line) {
    while (bad_back(line)) {
      del_back_line();
    }
    ins_back_line(line);
  }
  void add_front(pair<long long, long long> line) {
    while (bad_front(line)) {
      del_front_line();
    }
    ins_front_line(line);
  }
  pair<long long, long long> get_best_line(long long x) {
    if ((int)lines.size() == 1) {
      return lines[0];
    }
    int st = -1, dr = sect.size();
    while (dr - st > 1) {
      int mid = (st + dr) / 2;
      if (sect[mid] <= x) {
        st = mid;
      } else {
        dr = mid;
      }
    }
    return lines[dr];
  }
};
class UndoMinConvexHull {
 public:
  int len;
  vector<pair<long long, long long> > lines;
  vector<pair<pair<int, int>, pair<long long, long long> > > undo_log;
  UndoMinConvexHull() {
    len = 0;
    lines.clear();
    undo_log.clear();
  }
  void add_line(pair<long long, long long> line) {
    int st = -1, dr = len - 1;
    while (dr - st > 1) {
      int mid = (st + dr) / 2;
      if (get_sect(lines[mid], lines[mid + 1]) <= get_sect(lines[mid], line)) {
        st = mid;
      } else {
        dr = mid;
      }
    }
    dr++;
    if ((int)lines.size() <= dr) {
      lines.push_back({0, 0});
    }
    undo_log.push_back({{dr, len}, lines[dr]});
    lines[dr] = line;
    len = dr + 1;
  }
  void undo() {
    len = undo_log.back().first.second;
    lines[undo_log.back().first.first] = undo_log.back().second;
    undo_log.pop_back();
  }
  pair<long long, long long> best_line(long long x) {
    int st = -1, dr = len - 1;
    while (dr - st > 1) {
      int mid = (st + dr) / 2;
      if (get_sect(lines[mid], lines[mid + 1]) <= x) {
        st = mid;
      } else {
        dr = mid;
      }
    }
    return lines[dr];
  }
};
void merge_hulls(LinearMinConvexHull &a, LinearMinConvexHull &b) {
  if (a.lines.size() < b.lines.size()) {
    while (a.lines.size()) {
      b.add_front(a.lines.back());
      a.lines.pop_back();
    }
    a.sect.clear();
    a.lines.swap(b.lines);
    a.sect.swap(b.sect);
  } else {
    while (b.lines.size()) {
      a.add_back(b.lines.front());
      b.lines.pop_front();
    }
    b.sect.clear();
  }
}
int n, k;
int a[20002];
long long dp[102][20002];
int st[20002], len;
LinearMinConvexHull hulls[20002];
int main() {
  scanf("%d %d", &n, &k);
  int ma = 0;
  for (int i = 1; i <= n; i++) {
    scanf("%d", &a[i]);
    ma = max(ma, a[i]);
    dp[1][i] = 1LL * ma * i;
  }
  UndoMinConvexHull main_hull;
  for (int h = 2; h <= k; h++) {
    for (int i = 1; i <= n; i++) {
      st[++len] = a[i];
      hulls[len].add_front({-(i - 1), dp[h - 1][i - 1]});
      while (len > 1 && st[len - 1] <= st[len]) {
        main_hull.undo();
        merge_hulls(hulls[len - 1], hulls[len]);
        st[len - 1] = st[len];
        len--;
      }
      pair<long long, long long> line = hulls[len].get_best_line(a[i]);
      main_hull.add_line({a[i], 1LL * line.first * a[i] + line.second});
      line = main_hull.best_line(i);
      dp[h][i] = 1LL * line.first * i + line.second;
    }
    while (len) {
      hulls[len].lines.clear();
      hulls[len].sect.clear();
      len--;
    }
    while (main_hull.len) {
      main_hull.undo();
    }
  }
  printf("%lld\n", dp[k][n]);
  return 0;
}