#include <vector>
#include <algorithm>
#include <functional>
#include <queue>
#include <set>
#include <map>
#include <climits>
#include <cstring>
#include <iostream>
using namespace std;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
// Transform points to intervals [a, b] where a = min(r,c), b = max(r,c)
vector<pair<int, int>> points;
for (int i = 0; i < n; i++) {
int a = min(r[i], c[i]);
int b = max(r[i], c[i]);
points.push_back({a, b});
}
// Sort points by a (left coordinate)
sort(points.begin(), points.end());
// Remove points that are dominated
vector<pair<int, int>> filtered;
int maxB = -1;
for (int i = n - 1; i >= 0; i--) {
if (points[i].second > maxB) {
maxB = points[i].second;
filtered.push_back(points[i]);
}
}
reverse(filtered.begin(), filtered.end());
int N = filtered.size();
k = min(k, N);
// Now we have strictly increasing a and b
vector<int> A(N), B(N);
for (int i = 0; i < N; i++) {
A[i] = filtered[i].first;
B[i] = filtered[i].second;
}
// DP[i][j] = minimal cells to cover first i points with j photos
vector<vector<long long>> dp(N + 1, vector<long long>(k + 1, LLONG_MAX / 2));
dp[0][0] = 0;
// Cost function: covering points from l to r-1 with one photo
// The photo must cover from A[l] to B[r-1]
auto cost = [&](int l, int r) -> long long {
if (l >= r) return 0;
long long side = B[r-1] - A[l] + 1;
return side * side;
};
// For each k, use divide and conquer optimization
for (int j = 1; j <= k; j++) {
// Compute dp[i][j] from dp[t][j-1] + cost(t, i)
function<void(int, int, int, int)> solve = [&](int l, int r, int optL, int optR) {
if (l > r) return;
int mid = (l + r) / 2;
long long best = LLONG_MAX;
int bestPos = optL;
for (int t = optL; t <= min(optR, mid); t++) {
long long val = dp[t][j-1] + cost(t, mid);
if (val < best) {
best = val;
bestPos = t;
}
}
dp[mid][j] = best;
if (l != r) {
solve(l, mid - 1, optL, bestPos);
solve(mid + 1, r, bestPos, optR);
}
};
solve(j, N, j-1, N);
}
long long ans = LLONG_MAX;
for (int j = 1; j <= k; j++) {
ans = min(ans, dp[N][j]);
}
return ans;
}
int main() {
int n, m, k;
// Read input
cin >> n;
cin >> m;
cin >> k;
vector<int> r(n), c(n);
for (int i = 0; i < n; i++) {
cin >> r[i] >> c[i];
}
// Call the function
long long result = take_photos(n, m, k, r, c);
// Output result
cout << result << endl;
return 0;
}
