#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll N,M,K;
ll dp[100005],c1=0,v1,c2=1e6,v2,cnt[100005];
struct tacka{
ll x,y;/// X i Y su kao u matematici
} tniz[100005],niz[100005],tpp;
stack<tacka> S;
bool pox(tacka a,tacka b){
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
return a.y<b.y;
}
ll koliko(ll x,ll y,ll px,ll py){
ll r=abs(x-y);
ll d=r+1;
if((x-px)>=d)
return d*d;
ll a=d*d-(d-(x-px))*(d-(x-px));
return a;
}
struct funk{
ll offset,slope;
int id;
ll evaluiraj(ll gde){
return gde*slope+offset;
}
}pp;
vector<funk> C;
void dodaj(funk x){
C.push_back(x);
}
int koja(ll gde){
if(C.size()==0)
return 0;
int ret=0;
ll vred=C[0].evaluiraj(gde);
for(int i=1;i<C.size();i++){
ll v2=C[i].evaluiraj(gde);
if(v2<vred){
vred=v2;
ret=i;
}
}
return ret;
}
ll izracunaj(ll lmb){
dp[0]=0;
cnt[0]=0;
for(ll i=1;i<=N;i++){
dp[i]=dp[i-1]+koliko(niz[i].x,niz[i].y,niz[i-1].x,niz[i-1].y)-lmb;
cnt[i]=cnt[i-1]+1;
int j=koja(niz[i].x);
ll vred=koliko(niz[i].x,niz[j].y,niz[j-1].x,niz[j-1].y)+dp[j-1]-lmb;
if(vred<dp[i]){
dp[i]=vred;
cnt[i]=cnt[j-1]+1;
}
/// pp;
///d=x-niz[i].y+1;
if(-niz[i-1].x>=-niz[i].y+1){
/// (x-niz[i].y+1)*(x-niz[i].y+1)
/// x*x - 2*(niz[i].y+1) * x + (niz[i].y+1)*(niz[i].y+1)
pp.slope=- 2*(niz[i].y-1);
pp.offset=(niz[i].y-1)*(niz[i].y-1);
}
else{
///(d*d)-(d-(x-niz[i-1].x))*(d-(x-niz[i-1].x))
///(d-(x-niz[i-1].x))=(x-niz[i].y+1-(x-niz[i-1].x))=(x-niz[i].y+1-x+niz[i-1].x)=(-niz[i].y+1+niz[i-1].x)
///x*x - 2*(niz[i].y+1) * x + (niz[i].y+1)*(niz[i].y+1) -(-niz[i].y+1+niz[i-1].x)
pp.slope= - 2*(niz[i].y-1);
pp.offset=(niz[i].y-1)*(niz[i].y-1) -(-niz[i].y+1+niz[i-1].x)+dp[i];
}
dodaj(pp);
}
if(cnt[N]<=K and cnt[N]>c1){
c1=cnt[N];
v1=dp[N]+lmb*cnt[N];
}
if(cnt[N]>K and cnt[N]<c2){
c2=cnt[N];
v2=dp[N]+lmb*cnt[N];
}
return dp[N]+lmb*cnt[N];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
/*while(true){
ll a,b,c,d;
cin>>a>>b>>c>>d;
cout<<koliko(a,b,c,d)<<endl;
}*/
N=n;
M=m;
K=k;
for(ll i=1;i<=N;i++){
tniz[i].x=c[i-1]+1;
tniz[i].y=r[i-1]+1;
}
for(ll i=1;i<=N;i++)
if(tniz[i].x<tniz[i].y)
swap(tniz[i].x,tniz[i].y);
sort(tniz+1,tniz+1+N,pox);
tpp.x=-1;
tpp.y=-1e9;
S.push(tpp);
// cout<<N<<endl;
//for(ll i=1;i<=N;i++)
// cout<<tniz[i].x<<" "<<tniz[i].y<<endl;
for(ll i=1;i<=N;i++){
if(S.top().x==tniz[i].x)
continue;
while(S.top().y>=tniz[i].y)
S.pop();
S.push(tniz[i]);
}
for(ll i=1;i<=N;i++){
niz[i].x=0;
niz[i].y=0;
}
N=S.size()-1;
for(ll i=N;i>=1;i--){
niz[i]=S.top();
S.pop();
}
//cout<<N<<endl;
//for(ll i=1;i<=N;i++)
// cout<<niz[i].x<<" "<<niz[i].y<<endl;
if(K>N)
K=N;
niz[0].x=niz[0].y=-1e9;
ll dg=-M*M,ret=0,gg=0,sred;
while(dg<=gg){
sred=(dg+gg)/2;
izracunaj(sred);
if(cnt[N]<=K){
dg=sred+1;
ret=dg;
}
else
gg=sred-1;
}
ll res=v1;
res=min(res,v1+((v2-v1)/(c2-c1))*(K-c1));
dg=-M*M;
gg=ret;
ll v1,v2;
while(dg<=gg){
sred=(dg+gg)/2;
v1=izracunaj(sred-1);
v2=izracunaj(sred);
res=min(res,v1);
res=min(res,v2);
if(v2<v1)
dg=sred+1;
else
gg=sred-1;
}
return res;
}
