#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
#define ld long double
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 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;
deque<funk> C;
ld presek(funk a,funk b){
return (ld)(b.offset-a.offset)/(a.slope-b.slope);
}
void dodaj(funk x){
funk p1,p2;
while(C.size()>=2){
p1=C.back();
C.pop_back();
p2=C.back();
if(presek(x,p2)>=presek(p1,p2)){
C.push_back(p1);
break;
}
}
C.push_back(x);
}
funk koja(ll gde){
funk p1,p2;
while(C.size()>1){
p1=C.front();
C.pop_front();
p2=C.front();
if(p1.evaluiraj(gde)<p2.evaluiraj(gde)){
C.push_front(p1);
break;
}
}
return C[0];
}
ll izracunaj(ll lmb){
C.clear();
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)-lmb;
cnt[i]=cnt[i-1]+1;
ll mvred=1e18,gde=0;
//C.clear();
if(i!=1){
funk ff=koja(niz[i].x);
mvred=ff.evaluiraj(niz[i].x);
gde=ff.id;
if(mvred+niz[i].x*niz[i].x<dp[i]){
dp[i]=mvred+niz[i].x*niz[i].x;
cnt[i]=cnt[gde-1]+1;
}
}
pp.slope=-2*(niz[i].y-1);
pp.id=i;
if(-niz[i-1].x>=-niz[i].y+1)
pp.offset=(niz[i].y-1)*(niz[i].y-1)+dp[i-1]-lmb;
else
pp.offset=(niz[i].y-1)*(niz[i].y-1) - (-niz[i].y+1+niz[i-1].x)*(-niz[i].y+1+niz[i-1].x)+dp[i-1]-lmb;
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;
/* izracunaj(-8);
cout<<cnt[N]<<" "<<dp[N]<<endl;
return 0;*/
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;
}
// cout<<sred<<endl;
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;
}
