#include "aliens.h"
#include <iostream>
#include <algorithm>
#define long long long
using namespace std;
const int N = 1e5 + 2;
const long INF = 1e18;
struct TPoint { long x, y; };
inline long sqr(long x) { return x * x; }
int n, m, k;
TPoint a[N];
void Reduce()
{
for (int i = 1; i <= n; ++i)
if (a[i].x > a[i].y) swap(a[i].x, a[i].y);
sort(a + 1, a + 1 + n, [](TPoint p, TPoint q) { return p.x < q.x || (p.x == q.x && p.y > q.y); });
int new_n = 1;
for (int i = 2; i <= n; ++i)
if (a[i].y > a[new_n].y) a[++new_n] = a[i];
n = new_n;
for (int i = 1; i <= n; ++i) ++a[i].y; // we add every column by 1
}
inline long Cost(int i, int j)
{
int pre_h = max(0LL, a[i - 1].y - a[i].x);
int cur_h = a[j].y - a[i].x;
return sqr(cur_h) - sqr(pre_h);
}
long f[2][N];
bool Minimize(long &a, long b) { if (a <= b) return false; a = b; return true; }
struct THull
{
struct TLine {
long a, b;
long Eval(long x) { return a * x + b; }
};
double Intersect(TLine p, TLine q) { return (double) (q.b - p.b) / (p.a - q.a); }
int n = 0, lim = 1;
TLine st[N];
void AddLine(TLine p)
{
while (n >= 2 && n > lim && Intersect(st[n - 1], p) <= Intersect(st[n - 1], st[n])) --n;
st[++n] = p;
}
long Query(long x)
{
while (lim < n && x >= Intersect(st[lim], st[lim + 1])) ++lim;
return st[lim].Eval(x);
}
void Clear() { n = 0, lim = 1; }
} hull;
long Solve()
{
Reduce();
// for (int i = 1; i <= n; ++i) cerr << Cost(i, i) << ' ';
// cerr << '\n';
int cur = 1, pre = 0;
fill(f[cur] + 1, f[cur] + 1 + n, INF);
for (int j = 1; j <= k; ++j)
{
swap(cur, pre);
hull.Clear();
for (int i = 1; i <= n; ++i)
{
hull.AddLine({-a[i].x * 2, sqr(a[i].x) - sqr(max(0LL, a[i - 1].y - a[i].x)) + f[pre][i - 1]});
f[cur][i] = hull.Query(a[i].y) + sqr(a[i].y);
//cout << f[cur][i] << ' ';
}
//cout << '\n';
}
return f[cur][n];
}
long take_photos(int _n, int _m, int _k, vector<int> _r, vector<int> _c) {
n = _n, m = _m, k = _k;
for (int i = 0; i < _n; ++i) a[i + 1] = {_r[i], _c[i]};
return Solve();
}
