// Catling
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto operator<<(auto&o,auto p)->decltype(p.first,o){return o<<'('<<p.first<<", "<<p.second <<')';}
auto operator<<(auto&o,auto X)->decltype(X.end(),o){o<<'{';int i=2;for(auto e:X)o<<(", ")+i<<e,i=0;return o<<'}';}
#define LOG(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define LOG(X...)(void)0
#endif
typedef long long ll;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
#define all(X) (X).begin(),(X).end()
#define endl '\n'
#define size(X) X.size()
const ll INF = 9223372036854775806 / 4;
const ll MAX_N = 1e9+1;
const ll MOD = 1e9+7; // 998244353
int N, M, K;
vector<pair<int,int>> pointsArray;
vector<ll> A, B;
vector<ll> segmentTree;
void buildTree(int indexValue, int l, int R) {
if (l == R) {
segmentTree[indexValue] = B[l];
} else {
int middleIndex = (l + R) / 2;
buildTree(indexValue * 2, l, middleIndex);
buildTree(indexValue * 2 + 1, middleIndex + 1, R);
segmentTree[indexValue] = max(segmentTree[indexValue * 2], segmentTree[indexValue * 2 + 1]);
}
}
ll queryMax(int indexValue, int l, int R, int secondL, int secondR) {
if (secondR < l || R < secondL) return -INF;
if (secondL <= l && R <= secondR) return segmentTree[indexValue];
int middleIndex = (l + R) / 2;
return max(
queryMax(indexValue * 2, l, middleIndex, secondL, secondR),
queryMax(indexValue * 2 + 1, middleIndex + 1, R, secondL, secondR)
);
}
vector<ll> valueDP;
vector<int> segmentsDP;
ll lambdaPenalty;
void divideSolve(int L, int R, int optimalL, int optimalR) {
if (L > R) return;
int middleIndex = (L + R) / 2;
ll bestValue = INF;
int bestK = -1, bestSegment = 0;
int upperBound = min(optimalR, middleIndex - 1);
for (int j = optimalL; j <= upperBound; j++) {
ll maxValue = queryMax(1, 1, N, j + 1, middleIndex);
ll currentLength = maxValue - A[j + 1] + 1;
ll currentCost = currentLength * currentLength + lambdaPenalty;
ll candidateScore = valueDP[j] + currentCost;
int segmentsCounter = segmentsDP[j] + 1;
if (candidateScore < bestValue || (candidateScore == bestValue && segmentsCounter < bestSegment)) {
bestValue = candidateScore;
bestSegment = segmentsCounter;
bestK = j;
}
}
valueDP[middleIndex] = bestValue;
segmentsDP[middleIndex] = bestSegment;
divideSolve(L, middleIndex - 1, optimalL, bestK);
divideSolve(middleIndex + 1, R, bestK, optimalR);
}
pair<ll,int> runLambda(ll lam) {
lambdaPenalty = lam;
valueDP.assign(N + 1, INF);
segmentsDP.assign(N + 1, 0);
valueDP[0] = 0;
segmentsDP[0] = 0;
divideSolve(1, N, 0, N - 1);
return {valueDP[N], segmentsDP[N]};
}
void solveTestCase() {
cin >> N >> M >> K;
pointsArray.resize(N);
for (int i = 0; i < N; i++) {
int R, C;
cin >> R >> C;
int A = min(R, C);
int B = max(R, C);
pointsArray[i] = {A, B};
}
sort(pointsArray.begin(), pointsArray.end());
A.assign(N + 1, 0);
B.assign(N + 1, 0);
for (int i = 1; i <= N; i++) {
A[i] = pointsArray[i - 1].first;
B[i] = pointsArray[i - 1].second;
}
segmentTree.assign(4 * (N + 1), -INF);
buildTree(1, 1, N);
ll leftBound = 0, rightBound = (ll)2 * M * (ll)2 * M + 5;
while (leftBound < rightBound) {
ll middleIndex = leftBound + (rightBound - leftBound)/2;
auto [F, argumentMax] = runLambda(middleIndex);
if (argumentMax > K) leftBound = middleIndex + 1;
else rightBound = middleIndex;
}
auto [optimalValue, optimalCount] = runLambda(leftBound);
ll finalAnswer = optimalValue - leftBound * (ll) optimalCount;
cout << finalAnswer << endl;
return;
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int T = 1;
while(T--) {
solveTestCase();
}
return 0;
}
