#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';
}
