#include <bits/stdc++.h>
using namespace std;
template <typename T, const T id>
class CHT {
  struct Line {
    T a, b;
    Line(T a = 0, T b = 0) : a(a), b(b) {}
    T get(T x) { return a * x + b; }
  };
  struct Node {
    Line line;
    Node *lch, *rch;
    Node(Line line) : line(line), lch(nullptr), rch(nullptr) {}
  };

 private:
  const long long n;
  const vector<T> pos;
  Node *root;

 public:
  CHT(const vector<T> &pos) : n(pos.size()), pos(pos), root(nullptr) {}
  void insert(T a, T b) {
    Line line(a, b);
    root = modify(root, 0, n, line);
  }
  T query(T x) {
    cout << "query" << endl;
    long long t = lower_bound(pos.begin(), pos.end(), x) - pos.begin();
    assert(t < n && pos[t] == x);
    return sub(root, 0, n, t);
  }

 private:
  Node *modify(Node *p, long long lb, long long ub, Line &line) {
    if (!p) return new Node(line);
    if (p->line.get(pos[lb]) >= line.get(pos[lb]) &&
        p->line.get(pos[ub - 1]) >= line.get(pos[ub - 1]))
      return p;
    if (p->line.get(pos[lb]) <= line.get(pos[lb]) &&
        p->line.get(pos[ub - 1]) <= line.get(pos[ub - 1])) {
      p->line = line;
      return p;
    }
    long long mid = (lb + ub) / 2;
    if (p->line.get(pos[mid]) < line.get(pos[mid])) swap(p->line, line);
    if (p->line.get(pos[lb]) <= line.get(pos[lb]))
      p->lch = modify(p->lch, lb, mid, line);
    else
      p->rch = modify(p->rch, mid, ub, line);
    return p;
  }
  T sub(Node *p, long long lb, long long ub, long long t) {
    cout << lb << " " << ub << endl;
    if (!p) {
      cout << "return id" << endl;
      return id;
    }
    cout << 1 << endl;
    if (ub - lb == 1) return p->line.get(pos[t]);
    cout << 2 << endl;
    long long mid = (lb + ub) / 2;
    cout << 3 << endl;
    if (t < mid) {
      cout << 4 << endl;
      return max(p->line.get(pos[t]), sub(p->lch, lb, mid, t));
    }
    cout << 5 << endl;
    return max(p->line.get(pos[t]), sub(p->rch, mid, ub, t));
  }
};
signed main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(0);
  long long n;
  cin >> n;
  ;
  long long k;
  cin >> k;
  ;
  ;
  vector<long long> data(n);
  for (long long i = 0; i < n; i++) {
    cin >> data[i];
  }
  vector<long long> arr = data;
  sort((arr).begin(), (arr).end());
  arr.erase(unique((arr).begin(), (arr).end()), arr.end());
  vector<vector<long long> > dp(k + 1,
                                vector<long long>(n + 1, 1001000100010001000));
  dp[0][0] = 0;
  for (long long i = 0; i < k; i++) {
    CHT<long long, -1001000100010001000> funami(arr);
    for (long long a = 0; a < n; a++) {
      cout << "hoge" << endl;
      funami.insert(2 * data[a], -(dp[a][k] + data[a] * data[a]));
      cout << "hoge" << endl;
      dp[a + 1][i + 1] = data[a] * data[a] - funami.query(data[a]);
      cout << "hoge" << endl;
    }
  }
  cout << dp[k][n] << endl;
  return 0;
}
