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 long long LL_INF = (long long)2e18 + 5;
struct point {
  long long x, y;
  point() : x(0), y(0) {}
  point(long long _x, long long _y) : x(_x), y(_y) {}
};
struct reverse_monotonic_dp_hull {
  vector<point> points;
  int size() const { return (int)points.size(); }
  void clear() {
    points.clear();
    prev_x = LL_INF;
  }
  static long long floor_div(long long a, long long b) {
    return a / b - ((a ^ b) < 0 && a % b != 0);
  }
  static bool bad_middle(const point &a, const point &b, const point &c) {
    return floor_div(a.y - b.y, b.x - a.x) >= floor_div(b.y - c.y, c.x - b.x);
  }
  void insert(const point &p) {
    assert(size() == 0 || p.x >= points.back().x);
    if (size() > 0 && p.x == points.back().x) {
      if (p.y <= points.back().y) return;
      points.pop_back();
    }
    while (size() >= 2 &&
           bad_middle(points[points.size() - 2], points.back(), p))
      points.pop_back();
    points.push_back(p);
  }
  void insert(long long a, long long b) { insert(point(a, b)); }
  long long prev_x = LL_INF;
  long long query(long long x) {
    assert(x <= prev_x);
    prev_x = x;
    while (size() >= 2 && x * (points.back().x - points[size() - 2].x) <=
                              points[size() - 2].y - points.back().y)
      points.pop_back();
    return points.back().x * x + points.back().y;
  }
};
int N, K;
vector<long long> A;
vector<long long> dp, next_dp;
vector<long long> left_max, right_max;
void update(int start, int end) {
  if (start >= end) return;
  if (end - start == 1) {
    next_dp[end] = min(next_dp[end], dp[start] + A[start]);
    return;
  }
  int mid = (start + end) / 2;
  update(start, mid);
  left_max[mid] = right_max[mid] = -LL_INF;
  for (int i = mid - 1; i >= start; i--)
    left_max[i] = max(left_max[i + 1], A[i]);
  for (int i = mid; i < end; i++) right_max[i + 1] = max(right_max[i], A[i]);
  reverse_monotonic_dp_hull hull;
  for (int right = mid + 1, left = mid; right <= end; right++) {
    while (left >= start && right_max[right] >= left_max[left]) {
      hull.insert(-left, -dp[left]);
      left--;
    }
    if (hull.size() > 0)
      next_dp[right] = min(next_dp[right], -hull.query(-right_max[right]) +
                                               right * right_max[right]);
  }
  hull.clear();
  for (int right = end, left = start; right > mid; right--) {
    while (left <= mid && left_max[left] >= right_max[right]) {
      hull.insert(-left_max[left], left * left_max[left] - dp[left]);
      left++;
    }
    if (hull.size() > 0)
      next_dp[right] = min(next_dp[right], -hull.query(right));
  }
  update(mid + 1, end);
}
void update_dp() {
  left_max.assign(N + 1, -LL_INF);
  right_max.assign(N + 1, -LL_INF);
  next_dp.assign(N + 1, LL_INF);
  update(0, N);
  swap(dp, next_dp);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cin >> N >> K;
  A.resize(N);
  for (auto &a : A) cin >> a;
  dp.assign(N + 1, LL_INF);
  dp[0] = 0;
  for (int k = 0; k < K; k++) update_dp();
  cout << dp[N] << '\n';
}