#ifdef t9unkubj
#define _GLIBCXX_DEBUG
#include"debug.cpp"
//#include"template_no_debug.h"
#else
#define dbg(...) 199958
#endif
#include "aliens.h"
#pragma GCC optimize("O3")
using namespace std;
#include"bits/stdc++.h"
using ll=long long;
using ull=unsigned long long;
template<class T>using vc=vector<T>;
template<class T>using vvc=vc<vc<T>>;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define REP(i,j,n) for(ll i=(j);i<(ll)(n);i++)
#define DREP(i,n,m) for(ll i=(n);i>=(m);i--)
#define drep(i,n) for(ll i=((n)-1);i>=0;i--)
#define all(x) x.begin(),x.end()
#define rall(x) x.rbegin(),x.rend()
template<class T,class F>
bool chmin(T &x, F y){
if(x>y){
x=y;
return true;
}
return false;
}
template<class T, class F>
bool chmax(T &x, F y){
if(x<y){
x=y;
return true;
}
return false;
}
double pass_time=0;
template<class T,class F>
vector<T>monotone_minima(F&a,int h,int w,int ismax=0){//関数Fに対してminを求める
vector<T>res(h);
auto solve=[&](auto&solve,int l,int r,int x,int y)->void{//[x,y) [l,r)について解く
if(x>=y)return;
int coef=ismax?-1:1;
int mid=(x+y)/2;
pair<T,int>ans=make_pair(numeric_limits<T>::max()/2+1,l);
for(int i=l;i<r;i++){
ans=min(ans,make_pair(a(mid,i)*coef,i));
}
solve(solve,l,ans.second+1, x,mid);
solve(solve,ans.second,r, mid+1,y);
res[mid]=ans.first*coef;
};solve(solve,0,w,0,h);
return res;
}
//
template<class F>
pair<ll,int> monge_edge_solver(F&f,int n,int need_cnt=1,ll pena=0){
vc<ll>dp(n,(ll)1e18);
dp[0]={0};
auto dfs=[&](auto&dfs,int l,int r)->void{
if(l+1==r)return;
int mid=l+r>>1;
dfs(dfs,l,mid);
auto F2=[&](int i,int j)->ll{
i+=mid;
j+=l;
return f(j,i)+dp[j]+pena;
};
//j to i
auto R=monotone_minima<ll,decltype(F2)>(F2,r-mid,mid-l,0);
rep(i,R.size()){
chmin(dp[i+mid],R[i]);
}
dfs(dfs,mid,r);
};
dfs(dfs,0,n);
if(need_cnt){
return pair<ll,int>{dp.back(),monge_edge_solver(f,n,0,pena+1).first-dp.back()};
}
return {dp.back(),0};
}
template<class F>
ll monge_d_edge_shortest(F&f,int n,int d,ll inf=2e13){
ll ac=-inf,wa=inf;
while(wa-ac>1){
ll wj=ac+wa>>1;
if(monge_edge_solver(f,n,1,wj).second>=d)ac=wj;
else wa=wj;
}
return monge_edge_solver(f,n,0,ac).first-ac*d;
}
using S=pair<int,int>;
S op(S a,S b){
return max(a,b);
}
struct segtree{
int n;
vc<S>node;
segtree(int n):n(n),node(n*2,{-1e9,-1e9}){}
void set(int i,S x){
node[i+=n]=x;
while(i>>=1)node[i]=op(node[i*2],node[i*2+1]);
}
S prod(int l,int r){
l+=n,r+=n;
S res={-1e9,-1e9};
while(l<r){
if(l&1)res=op(res,node[l++]);
if(r&1)res=op(res,node[--r]);
l/=2,r/=2;
}
return res;
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
set<pair<int,int>>nw;
rep(i,n){
if(r[i]-c[i]<0){
swap(c[i],r[i]);
}
nw.insert({c[i],r[i]});
}
n=nw.size();
c=r=vc<int>(n);
int now=0;
for(auto&x:nw){
c[now]=x.first;
r[now]=x.second;
now++;
}
vc<set<pair<int,int>>>is(m);
rep(i,n){
is[r[i]].insert({c[i],i});
}
dbg(r,c);
segtree seg(m);
auto modify=[&](int i){
if(is[i].empty())seg.set(i,{-1e9,-1e9});
else seg.set(i,{(*is[i].rbegin()).first,i});
};
rep(i,m){
modify(i);
}
vc<int>used(n);
rep(i,n){
if(used[i])continue;
is[r[i]].erase(pair<int,int>{c[i],i});
modify(r[i]);
int l1=c[i];
int r1=r[i];
while(1){
auto it=seg.prod(l1,r1+1);
if(it.first<c[i])break;
auto tar=*is[it.second].rbegin();
used[tar.second]=1;
is[it.second].erase(tar);
modify(it.second);
}
is[r[i]].insert(pair<int,int>{c[i],i});
modify(r[i]);
}
vc<pair<int,int>>Rs;
rep(i,n){
if(!used[i]){
Rs.push_back({r[i],c[i]});
}
}
sort(all(Rs));
n=Rs.size();
r=c=vc<int>(n);
rep(i,n)tie(r[i],c[i])=Rs[i];
dbg(r,c);
ll inf=2e18;
//i から j へ遷移
//⇔[i , j-1] を使う
auto dec=[&](int i){
if(i==0)return 0ll;
ll r1=r[i-1];
ll c1=c[i];
return max(0ll,r1-c1+1)*max(0ll,r1-c1+1);
};
auto cost=[&](int i,int j)->ll{
if(j-1<0||i>j-1)return inf;
int e1=(r[j-1]-c[i]+1);
ll ans=ll(e1)*e1-dec(i);
return ans;
};
chmin(k,n);
auto r1=monge_d_edge_shortest(cost,n+1,k);
auto r2=monge_edge_solver(cost,n+1);
if(r2.second<=k)chmin(r1,r2.first);
return r1;
}
void run(){
int n,m,k;
cin>>n>>m>>k;
vc<int>r(n),c(n);
rep(i,n)cin>>r[i]>>c[i];
dbg(take_photos(n,m,k,r,c));
}
/*
int main(){
#ifdef t9unkubj
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
run();
}
*/
