#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 mid=(x+y)/2;
pair<T,int>ans=pair<T,int>({(ll)4e18/2+1,4e18},l);
for(int i=l;i<r;i++){
ans=min(ans,make_pair(a(mid,i),i));
}
solve(solve,l,ans.second+1,x,mid);
solve(solve,ans.second,r,mid+1,y);
res[mid]=ans.first;
};solve(solve,0,w,0,h);
return res;
}
//
template<class F>
ll monge_d_edge_shortest(F&f,int n,int d,ll inf=2e13){
ll ac=-inf,wa=inf;
auto get=[&](ll wj){
using P=pair<ll,int>;
vc<P>dp(n,P{1e18,1e9});
dp[0]={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)->P{
i+=mid;
j+=l;
return P{f(j,i)+dp[j].first+wj,dp[j].second-1};
};
//j to i
auto R=monotone_minima<P,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(wj==0)dbg(dp);
return dp.back();
};
while(wa-ac>1){
ll wj=ac+wa>>1;
if(-get(wj).second>=d)ac=wj;
else wa=wj;
}
return get(ac).first-ac*d;
}
template<class F>
pair<ll,ll> monge_edge_shortest2(F&f,int n){
auto get=[&](){
using P=pair<ll,int>;
vc<P>dp(n,P{1e18,-1e9});
dp[0]={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)->P{
i+=mid;
j+=l;
return P{f(j,i)+dp[j].first,dp[j].second+1};
};
//j to i
auto R=monotone_minima<P,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);
return dp.back();
};
auto res=get();
return res;
}
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];
ll inf=2e18;
//i から j へ遷移
//⇔[i , j-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);
return ll(e1)*e1;
};
chmin(k,n);
auto r1=monge_d_edge_shortest(cost,n+1,k);
auto r2=monge_edge_shortest2(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();
}*/
