#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long const INF=1e18;
struct interval{
int l,r;
bool operator<(interval ot){
if(l!=ot.l)
return l<ot.l;
return r>ot.r;
}
}intv[100005];
long long diag[2000005];
void maxself(long long& x,long long val){
if(x<val)
x=val;
}
void minself(long long& x,long long val){
if(x>val)
x=val;
}
long long p2(int nr){
return 1LL*nr*nr;
}
struct line{
long long a,b;
int cnt;
};
long double inters(line l1,line l2){
return 1.0*(l2.b-l1.b)/(l1.a-l2.a);
}
struct answer{
long long val;
int cnt;
bool operator<(answer ot){
if(val!=ot.val)
return val<ot.val;
return cnt>ot.cnt;
}
};
answer eval(line lin,long long x){
return {lin.a*x+lin.b,lin.cnt};
}
struct CHT{
deque<line>deq;
void init(){
while(!deq.empty())
deq.pop_back();
}
void add(line lin){
while(deq.size()>=2 && inters(lin,deq.back())<inters(deq[deq.size()-2],deq.back()))
deq.pop_back();
deq.push_back(lin);
}
answer query(long long x){
answer ans={INF,0};
while(1){
answer cand=eval(deq[0],x);
if(cand<ans)
ans=cand;
if(deq.size()>=2 && inters(deq[0],deq[1])<=1.0*x)
deq.pop_front();
else
break;
}
return ans;
}
}cht;
answer get_dp(long long lambda,int total){
cht.init();
cht.add({-2*intv[1].l,p2(intv[1].l),0});
int i;
answer ans;
for(i=1;i<=total;++i){
ans=cht.query(intv[i].r);
ans.val+=p2(intv[i].r)+lambda;
++ans.cnt;
cht.add({-2*intv[i+1].l,p2(intv[i+1].l)-p2(max(0,intv[i].r-intv[i+1].l))+ans.val,ans.cnt});
}
return ans;
}
long long take_photos(int n,int m,int k,vector<int>r,vector<int>c){
int i;
for(i=0;i<2*m-1;++i)
diag[i]=-1;
for(i=0;i<n;++i){
int lin=r[i];
int col=c[i];
maxself(diag[lin+col],abs(lin-col));
}
int total=0;
for(i=0;i<2*m-1;++i)
if(diag[i]>-1)
intv[++total]={(i-(int)diag[i])/2,(i+(int)diag[i])/2+1};
sort(intv+1,intv+total+1);
int new_total=0;
intv[0]={-1,-1};
for(i=1;i<=total;++i)
if(intv[new_total].r<intv[i].r)
intv[++new_total]=intv[i];
total=new_total;
/// [)
long long st=0,dr=1e18;
while(dr-st>1){
long long mij=(st+dr)/2;
answer ans=get_dp(mij,total);
if(ans.cnt>=k)
st=mij;
else
dr=mij;
}
return get_dp(st,total).val-st*k;
}
