#include<bits/stdc++.h>
#define fi first
#define se second
#define endl "\n"
#define ii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
pair<int, int> a[N];
long long l[N], r[N], f[N], g[N];
struct line {
long long m, c;
int idx;
long long eval(long long x) { return m * x + c; }
long long cut(line l) {
return (c - l.c) / (l.m - m);
}
};
struct CHT {
line s[N];
int st = 1, ed = 0;
void add(line cur) {
// cout << st << " " << ed << endl;
while (ed - st + 1 >= 2 && cur.cut(s[ed]) <= s[ed].cut(s[ed - 1])) --ed;
s[++ed] = cur;
}
line get(long long x) {
while (ed - st + 1 >= 2 && s[st].eval(x) > s[st + 1].eval(x)) st++;
return s[st];
}
};
long long take_photos(int n, int m, int k, std::vector<int> RR, std::vector<int> CC) {
for(int i = 0; i < n; i++) {
a[i] = make_pair(RR[i], CC[i]);
if (a[i].fi > a[i].se) swap(a[i].fi, a[i].se);
}
sort(a, a + n, [] (const ii &A, const ii &B) {
if (A.fi != B.fi) return A.fi < B.fi;
return A.se > B.se;
});
int n2 = 0, mx = -1;
for(int i = 0; i < n; i++) if (a[i].se > mx) {
mx = a[i].se;
++n2;
l[n2] = a[i].fi;
r[n2] = a[i].se;
}
n = n2;
r[0] = -1;
long long L = 0, R = 1e18, res = 1e18;
while (L <= R) {
long long mid = L + R >> 1;
CHT cht;
for(int i = 1; i <= n; i++) {
long long cost = (l[i] <= r[i - 1]) ? (r[i - 1] - l[i] + 1) * (r[i - 1] - l[i] + 1) : 0;
line cur = {-2LL * l[i], f[i - 1] - cost + l[i] * l[i], i - 1};
cht.add(cur);
line opt = cht.get(r[i] + 1);
g[i] = g[opt.idx] + 1;
f[i] = opt.eval(r[i] + 1) + (r[i] + 1) * (r[i] + 1) + mid;
}
if (g[n] <= k) {
res = f[n] - mid * k;
R = mid - 1;
}
else L = mid + 1;
}
return res;
}
#ifdef ngu
int main() {
if (fopen ("task.inp", "r")) {
freopen ("task.inp", "r", stdin);
freopen ("task.out", "w", stdout);
}
int n, m, k; cin >> n >> m >> k;
vector<int> r(n), c(n);
for(int i = 0; i < n; i++) cin >> r[i] >> c[i];
cout << take_photos(n, m, k, r, c);
// cout << take_photos(5, 7, 3, {0, 4, 4, 4, 4}, {3, 4, 6, 5, 6});
// cout << take_photos(2, 6, 2, {1, 4}, {4, 1});
}
#endif // ngu
