#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int M=1e6+10;
const int N=1e5+10;
const int INFi=1e9;
const ll INFl=1e12;
int jump[N][18],t[N],mini[M],pot[N],l;
pair<ll,int> dp[N];
ll res=INFl;
bitset<N>vis;
bool diag(int a,int b){
return a>=b;
}
int minv(int a,int b){
int dl=b-a+1;
return min(jump[b][pot[dl]],jump[a+(1<<pot[dl])-1][pot[dl]]);
}
ll cnt(int i,int j){
int mm=minv(i+1,j);
return dp[i].fi+(ll)(t[j]-mm+1)*(ll)(t[j]-mm+1);
}
int bs(int a,int b,int pocz,int kon){
int sr,res=kon+1;
while(pocz<=kon){
sr=(pocz+kon)>>1;
ll val1=cnt(a,sr),val2=cnt(b,sr);
if(val1<val2 or (val1==val2 and dp[a].se<=dp[b].se)) res=sr,kon=sr-1;
else pocz=sr+1;
}
return res;
}
bool check(ll c,int k){
set<int> curr;
set<pair<int,int> >act;
curr.insert(1);
dp[1]={((ll)t[1]-jump[1][0]+1)*(ll)(t[1]-jump[1][0]+1)+(ll)c,1};
act.insert({2,0});
for(int i=1;i<=l;i++) vis[i]=0;
while(1){
auto it=act.begin();
pair<int,int>v=*it;
act.erase(it);
if(v.fi>l) break;
if(v.se<0){
v.se*=(-1);
if(vis[v.se]) continue;
vis[v.se]=1;
auto it2=curr.lower_bound(v.se);
it2--;
int mn=*it2;
it2++,it2++;
if(it2!=curr.end()){
int wi=*it2;
act.insert({bs(mn,wi,v.fi,l),-wi});
}
it2--;
curr.erase(it2);
}else{
auto it2=curr.end();
it2--;
ll val=cnt(*it2,v.fi)+c,val2=minv(1,v.fi);
if((ll)(t[v.fi]-val2+1)*(ll)(t[v.fi]-val2+1)+c<=val) dp[v.fi]={(ll)(t[v.fi]-val2+1)*(ll)(t[v.fi]-(ll)val2+1)+c,1};
else dp[v.fi]={val,dp[*it2].se+1};
act.insert({bs(*it2,v.fi,v.fi+1,l),-v.fi});
act.insert({v.fi+1,0});
curr.insert(v.fi);
}
}
if(dp[l].se<=k){
res=min(res,dp[l].fi-c*(ll)dp[l].se);
return 1;
}
return 0;
}
ll take_photos(int n,int m,int k,vi r,vi c){
for(int i=1;i<=m;i++) mini[i]=INFi;
for(int i=1;i<=n;i++){
r[i-1]++,c[i-1]++;
if(diag(r[i-1],c[i-1])) mini[r[i-1]]=min(mini[r[i-1]],c[i-1]);
else mini[c[i-1]]=min(mini[c[i-1]],r[i-1]);
}
for(int i=1;i<=m;i++){
if(mini[i]!=INFi){
t[++l]=i;
jump[l][0]=mini[i];
for(int j=1;l-(1<<j)+1>=1;j++) jump[l][j]=min(jump[l][j-1],jump[l-(1<<(j-1))][j-1]);
}
}
int wsk=0;
for(int i=1;i<=l;i++){
pot[i]=wsk;
if((1<<wsk)==i/2) wsk++;
}
ll pocz=0,kon=INFl;
while(pocz<=kon){
ll sr=(pocz+kon)>>1;
if(check(sr,k)) kon=sr-1;
else pocz=sr+1;
}
return res;
}
/*int main(){
int n,m,k;
cin>>n>>m>>k;
vi r,c;
for(int i=1,a,b;i<=n;i++){
cin>>a>>b;
r.push_back(a),c.push_back(b);
}
cout<<take_photos(n,m,k,r,c)<<"\n";
}*/
