#define JUDGE
#ifndef JUDGE
#include "aliens.h"
#endif // JUDGE
#include "bits/stdc++.h"
using namespace std;
typedef pair <int, int> pii;
vector <pii> range;
const long long INF = 1e16;
bool comp(pii a, pii b) {
if(a.first == b.first) {
return a.second > b.second;
} else {
return a.first < b.first;
}
}
long long count(int x, int y) {
if(x <= y) return 1LL * (y - x + 1) * (y - x + 1);
return 0;
}
long long dp[2][50005];
vector <long long> M;
vector <long long> C;
int pointer;
bool bad(int x, int y, int z) {
if(M[y] == M[z]) return true;
return (C[y] - C[z]) * (M[z] - M[x]) <= (C[x] - C[z]) * (M[z] - M[y]);
}
void addLine(long long m, long long c) {
if(!M.empty() && M.back() == m && C.back() < c) return ;
M.push_back(m);
C.push_back(c);
while(M.size() >= 3 && bad(M.size() - 3, M.size() - 2, M.size() - 1)) {
M.erase(M.end() - 2);
C.erase(C.end() - 2);
}
}
long long query(long long x) {
if(M.empty()) return INF;
if(pointer >= M.size()) {
pointer = M.size() - 1;
}
while(pointer + 1 < M.size() && M[pointer] * x + C[pointer] >= M[pointer + 1] * x + C[pointer + 1]) {
pointer++;
}
return M[pointer] * x + C[pointer];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
set <pii> all;
for(int i = 0; i < n; i++) {
int x = min(r[i], c[i]);
int y = max(r[i], c[i]);
all.insert(make_pair(x, y));
}
vector <pii> aux (all.begin(), all.end());
const int inf = 1e8;
multiset <int> s;
vector <pii> sweep;
for(int i = 0; i < (int) aux.size(); i++) {
sweep.push_back(make_pair(aux[i].first, inf));
sweep.push_back(make_pair(aux[i].second, aux[i].first));
}
sort(sweep.begin(), sweep.end(), comp);
for(int i = 0; i < (int) sweep.size(); i++) {
if(sweep[i].second == inf) {
s.insert(sweep[i].first);
} else {
if(*s.begin() == sweep[i].second) {
if(s.size() == 1 || *(++s.begin()) != sweep[i].second) {
range.push_back(pii(sweep[i].second, sweep[i].first));
}
}
s.erase(s.find(sweep[i].second));
}
}
range.push_back(make_pair(-1, -1));
sort(range.begin(), range.end());
int sz = range.size() - 1;
memset(dp, 0, sizeof dp);
for(int i = 1; i <= sz; i++) {
dp[0][i] = INF;
}
int ro = 0;
for(int i = 1; i <= k; i++) {
ro ^= 1;
M.clear();
C.clear();
pointer = 0;
for(int j = 1; j <= sz; j++) {
dp[ro][j] = INF;
if(dp[ro ^ 1][j - 1] < INF) addLine(-2LL * range[j].first, 1LL * range[j].first * range[j].first + dp[ro ^ 1][j - 1] - count(range[j].first, range[j-1].second));
dp[ro][j] = min(dp[ro][j], query(range[j].second + 1) + 1LL * (range[j].second + 1) * (range[j].second + 1));
/*
for(int l = 1; l <= j; l++) {
dp[ro][j] = min(dp[ro][j], dp[ro ^ 1][l - 1] + count(range[l].first, range[j].second) - count(range[l].first, range[l-1].second));
dp[]
}
*/
}
}
return dp[ro][sz];
}
#ifndef JUDGE
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);
return 0;
}
#endif // JUDGE
