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;
long long int power(long long int x, long long int y, long long int m) {
  if (y == 0) return 1;
  long long int a = power(x, y / 2, m);
  if (y % 2) {
    return (a * ((a * x) % m)) % m;
  } else {
    return (a * a) % m;
  }
}
long long int mod_inverse(long long int x, long long int m) {
  return power(x, m - 2, m);
}
long long int fact(long long int n, long long int m) {
  if (n <= 1) return 1;
  return (fact(n - 1, m) * n) % m;
}
long long int ncr(long long int n, long long int r, long long int m) {
  if (r > n) return 0;
  long long int n1 = 1, d1 = 1, d2 = 1;
  n1 = fact(n, m);
  d1 = fact(r, m);
  d2 = fact(n - r, m);
  long long int ans = mod_inverse((d1 * d2) % m, m);
  ans = (ans * n1) % m;
  return ans;
}
template <typename T>
class sparse_table {
 public:
  vector<T> a;
  int n, h;
  vector<vector<T> > dp;
  vector<int> pre_log2;
  void build() {
    for (int i = 1; i <= n; ++i) dp[i][0] = a[i];
    for (int j = 1; (1 << j) <= n; ++j) {
      int k = (1 << j);
      for (int i = 1; i + k - 1 <= n; ++i) {
        dp[i][j] = min(dp[i][j - 1], dp[i + (1 << (j - 1))][j - 1]);
      }
    }
  }
  sparse_table() {}
  sparse_table(vector<T> aa, int len) : a(aa) {
    n = len;
    h = ceil(log2(n));
    dp = vector<vector<T> >(n + 1, vector<T>(h + 1, 0));
    build();
    pre_log2.resize(n + 1);
    int val = 1;
    pre_log2[1] = 0;
    for (int i = 2; i <= n; ++i) {
      if (i >= val * 2) {
        pre_log2[i] = pre_log2[i - 1] + 1;
        val *= 2;
      } else {
        pre_log2[i] = pre_log2[i - 1];
      }
    }
  }
  T find(int l, int r) {
    if (l > r) swap(l, r);
    int d = (r - l + 1);
    int lg_d;
    lg_d = pre_log2[d];
    return min(dp[l][lg_d], dp[r - (1 << lg_d) + 1][lg_d]);
  }
};
struct line {
  long long int m, c;
  line(long long int mm, long long int cc) {
    m = mm;
    c = cc;
  }
  line() { m = c = 0; }
  long long int value(long long int x) { return m * x + c; }
};
bool cmp_line(line& l1, line& l2) { return l1.m <= l2.m; }
class linear_min_hull {
 public:
  deque<line> qu_line;
  deque<long long int> qu;
  long long int min_x, max_x;
  linear_min_hull(long long int mn, long long int mx) {
    min_x = mn;
    max_x = mx;
  }
  void insert_back(line l) {
    line t = qu_line.back();
    long long int p = qu.back();
    while (qu.size() > 1 && ((l.c - t.c) <= p * (t.m - l.m))) {
      qu.pop_back();
      qu_line.pop_back();
      t = qu_line.back();
      p = qu.back();
    }
    t = qu_line.back();
    if (t.m == l.m) {
      if (l.c <= t.c) {
        qu_line.pop_back();
        qu_line.push_back(l);
      }
      return;
    }
    double num = l.c - t.c, denum = t.m - l.m;
    long long int x = ceil(num / denum);
    qu_line.push_back(l);
    qu.push_back(x);
  }
  void insert_front(line l) {
    line t = qu_line.front();
    long long int p = max_x;
    if (qu.size() > 1) {
      p = qu.at(1) - 1;
    }
    while (qu.size() > 1 && ((t.c - l.c) >= p * (l.m - t.m))) {
      qu.pop_front();
      qu_line.pop_front();
      t = qu_line.front();
      p = max_x;
      if (qu.size() > 1) {
        p = qu.at(1) - 1;
      }
    }
    t = qu_line.front();
    if (t.m == l.m) {
      if (t.c >= l.c) {
        qu_line.pop_front();
        qu_line.push_front(l);
      }
      return;
    }
    double num = t.c - l.c, denum = l.m - t.m;
    long long int x = ceil(num / denum);
    qu.pop_front();
    qu.push_front(x);
    qu.push_front(min_x);
    qu_line.push_front(l);
  }
  void insert(line l) {
    if (qu.size() == 0) {
      qu_line.push_back(l);
      qu.push_back(min_x);
      return;
    }
    if (qu_line.back().m >= l.m)
      insert_back(l);
    else if (l.m >= qu_line.front().m)
      insert_front(l);
  }
  long long int find(long long int x) {
    auto itr = upper_bound((qu).begin(), (qu).end(), x);
    auto it = qu.begin();
    int ix = (itr - it) - 1;
    line l = qu_line.at(ix);
    return l.value(x);
  }
  bool empty() { return qu.empty(); }
};
class solver {
 public:
  int n, k;
  vector<long long int> a, prv, dp, arr;
  sparse_table<long long int> cost;
  void recur(int l, int r) {
    if (l == r) {
      dp[l] = 1000000000000000001ll;
      return;
    }
    int m = (l + r) / 2;
    recur(l, m);
    recur(m + 1, r);
    arr[m + 1] = a[m + 1];
    for (int i = m + 2; i <= r; ++i) arr[i] = max(arr[i - 1], a[i]);
    arr[m] = a[m];
    for (int i = m - 1; i >= l; --i) arr[i] = max(arr[i + 1], a[i]);
    linear_min_hull o(-100000000000ll, 100000000000ll);
    long long int j = l + 1;
    for (int i = r; i >= m + 1; --i) {
      while (j <= m && arr[j] >= arr[i]) {
        if (prv[j - 1] != 1000000000000000001ll)
          o.insert(
              line(arr[j], prv[j - 1] - ((long long int)(j - 1)) * arr[j]));
        j++;
      }
      if (!o.empty()) dp[i] = min(dp[i], o.find(i));
    }
    linear_min_hull o1(-100000000000ll, 100000000000ll);
    if (prv[m] != 1000000000000000001ll)
      o1.insert(line((long long int)(-1 * m), prv[m]));
    j = m;
    for (int i = m + 1; i <= r; ++i) {
      while (j > l && arr[j] < arr[i]) {
        if (prv[j - 1] != 1000000000000000001ll)
          o1.insert(line((long long int)(-1 * (j - 1)), prv[j - 1]));
        j--;
      }
      if (!o1.empty())
        dp[i] = min(dp[i], o1.find(arr[i]) + (long long int)(i)*arr[i]);
    }
  }
  void solve() {
    cin >> n >> k;
    a.resize(n + 1);
    dp.resize(n + 1);
    prv.resize(n + 1);
    arr.resize(n + 1);
    for (int i = 1; i <= n; ++i) cin >> a[i];
    cost = sparse_table<long long int>(a, n);
    long long int mx = a[1];
    for (int i = 1; i <= n; ++i) {
      mx = max(mx, a[i]);
      prv[i] = ((long long int)(i)) * mx;
    }
    dp = prv;
    for (int i = 2; i <= k; ++i) {
      recur(1, n);
      prv = dp;
    }
    cout << dp[n] << '\n';
  }
};
int main() {
  int test = 1;
  while (test--) {
    solver o;
    o.solve();
  }
}