#include <bits/stdc++.h>
#define int long long
#define FOR(var,bound) for(int var = 0; var < bound; var++)
#define FORB(var,lb,ub) for (int var = lb; var < ub; var++)
#define FORR(var,bound) for(int var = bound-1; var >= 0; var--)
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vector<int>> vvi;
typedef pair<int, int> pii;
vector<pii> ranges;
int rangeEnds[100000];
int prefixMax[100000];
int N;
//int dp[4005][4005];
//int opt[4005][4005];
vvi dp, opt;
int solve(int idx, int photosRemaining, int lowerBound, int upperBound) {
if (idx == N) return 0;
if (photosRemaining == 0) return 1e15;
if (dp[idx][photosRemaining] != -1) return dp[idx][photosRemaining];
if (rangeEnds[idx] >= ranges[idx].second) {
cout << "ERROR!" << endl;
}
int penalty = rangeEnds[idx] < ranges[idx].first ? 0 : (rangeEnds[idx] - ranges[idx].first+1)*(rangeEnds[idx] - ranges[idx].first+1);
int res = 1e15;
int minPos = -1;
for (int i = max(idx, lowerBound); i <= upperBound; i++) {
int e = prefixMax[i];
int s = (e - ranges[idx].first+1)*(e - ranges[idx].first+1) - penalty;
int score = solve(i + 1, photosRemaining - 1, -1, -1) + s;
if (score < res) {
minPos = i;
res = score;
}
}
opt[idx][photosRemaining] = minPos;
return dp[idx][photosRemaining] = res;
}
void solveAll(int l, int r, int photosRemaining, int lowerBound, int upperBound) {
if (l > r) return;
if (l == r) {
solve(l, photosRemaining, lowerBound, upperBound);
}
int m = (l + r) / 2;
solve(m, photosRemaining, lowerBound, upperBound);
solveAll(l, m - 1, photosRemaining, lowerBound, opt[m][photosRemaining]);
solveAll(m + 1, r, photosRemaining, opt[m][photosRemaining], upperBound);
}
int64_t take_photos(int32_t n, int32_t m, int32_t k, vector<int32_t> r, vector<int32_t> c) {
N = n;
//memset(dp, -1, sizeof(dp));
dp.resize(N, vi(k + 1, -1));
opt.resize(N, vi(k + 1));
vector<pii> rawRanges(n);
FOR(i, n) {
rawRanges[i] = {
min(r[i], c[i]),
max(r[i], c[i])
};
}
sort(rawRanges.begin(), rawRanges.end());
int e = -1;
FOR(i, n) {
rangeEnds[i] = e;
e = max(e, rawRanges[i].second);
}
FOR(i, n) {
if (rangeEnds[i] < rawRanges[i].second) {
ranges.push_back(rawRanges[i]);
}
}
N = ranges.size();
e = -1;
FOR(i, N) {
rangeEnds[i] = e;
e = max(e, ranges[i].second);
prefixMax[i] = e;
}
for (int i = 1; i <= k; i++) {
solveAll(0, N - 1, i, 0, N - 1);
}
return solve(0, k, -1, -1);
}
#ifdef LOCAL_TEST
signed main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, k;
cin >> n >> m >> k;
vector<int32_t> r(n), c(n);
FOR(i, n) {
cin >> r[i] >> c[i];
}
cout << take_photos(n, m, k, r, c) << endl;
}
#endif
