#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto&operator<<(auto &o, pair<auto, auto> p) {o << "(" << p.first << ", " << p.second << ")"; return o;}
auto operator<<(auto&o,auto x)->decltype(x.end(),o){o<<"{"; for(auto e : x) o<<e<<", "; return o<<"}";}
#define debug(X) cerr << "["#X"]: " << X << '\n';
#else
#define cerr if(0)cout
#define debug(X) ;
#endif
using ll = long long;
using ld = long double;
#define all(v) (v).begin(), (v).end()
#define ssize(x) int(x.size())
#define fi first
#define se second
#define mp make_pair
#define eb emplace_back
const ll inf = 1e15;
ll sq(int x) {
return ll(x)*x;
}
struct line {
ll a, b;
line(ll x = 0, ll y = 0): a(x), b(y) {}
};
ld intersection(line l1, line l2) {
assert(l1.a != l2.a);
return ld(l2.b - l1.b) / ld(l1.a - l2.a);
}
struct CHT {
deque<line> q;
CHT() {}
void add(line l) {
while (ssize(q) >= 2 && intersection(l, q[ssize(q)-2]) <= intersection(q[ssize(q)-2], q[ssize(q)-1])) q.pop_back();
q.eb(l);
}
ll query(ll x) {
if (!ssize(q)) return inf;
while (ssize(q) >= 2 && x >= intersection(q[0], q[1])) q.pop_front();
return q[0].a * x + q[0].b;
}
};
long long take_photos(int n, int m, int k, std::vector<int> x, std::vector<int> y) {
for (int i = 0; i < n; ++i)
if (x[i] > y[i]) swap(x[i], y[i]);
debug(x);
debug(y);
vector<int> nx, ny;
vector<int> idx(n);
iota(all(idx), 0);
sort(all(idx), [&](int a, int b) {
return mp(y[a], x[a]) > mp(y[b], x[b]);
});
debug(idx);
int mx = m+1;
for (int i : idx) {
if (mx <= x[i]) continue;
debug(i);
debug(mx);
debug(mp(x[i], y[i]));
nx.eb(x[i]); ny.eb(y[i]);
mx = x[i];
}
n = ssize(nx);
x = nx; y = ny;
reverse(all(x));
reverse(all(y));
debug(n);
debug(x);
debug(y);
debug(inf);
vector<vector<ll>> dp(n+1, vector<ll>(k+1, inf));
dp[0][0] = 0;
for (int j = 1; j <= k; ++j) {
CHT cht;
for (int i = 1; i <= n; ++i) {
cht.add(line(-2 * (x[i-1]-1), sq(x[i-1]-1) + dp[i-1][j-1] - (i - 2 >= 0 ? sq(max(0, y[i-2] - x[i-1]+1)) : 0ll) ));
dp[i][j] = sq(y[i-1]) + cht.query(y[i-1]);
// for (int l = 0; l < i; ++l) {
// dp[i][j] = min(dp[i][j], dp[l][j-1] + sq(y[i-1] - x[l] + 1) - (l - 1 >= 0 ? sq(max(0, y[l-1] - x[l]+1)) : 0ll) );
// }
}
}
debug(dp);
ll res = inf;
for (int j = 0; j <= k; ++j) res = min(res, dp[n][j]);
return res;
}
#ifdef LOCAL
int main() {
int n, m, k;
assert(3 == scanf("%d %d %d", &n, &m, &k));
std::vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
assert(2 == scanf("%d %d", &r[i], &c[i]));
}
long long ans = take_photos(n, m, k, r, c);
printf("%lld\n", ans);
}
#endif
