#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,k,pi,pr[1000009],pas,K,B,X,lef,rig,mid,LEF1,LEF2,RIG1,RIG2;
long long bofx[1000009];
pair <long long, long long> p[1000009],pp[1000009];
//vector <vector <long long> > dp,dp2;
vector <long long> dp,dp2;
deque <pair <pair <long long, long long> , long long> > de;
pair <long long, long long> P;
pair <long long, long long> DO(long long cost){
for(i=0; i<=a+1; i++){
dp[i]=a*a+3+cost*(a+M);
}
dp[0]=0;dp2[0]=0;
de.clear();
for(i=1; i<=a; i++){
ii=i-1;
K=(-2LL)*ii;B=dp[pr[ii]]+ii*ii;
if(pr[ii]>ii) B-=(pr[ii]-ii)*(pr[ii]-ii);
K=-K;B=-B;
while(de.size()&&de.back().first.second<=B) de.pop_back();
while(de.size()>=2){
zx=(de[de.size()-1].first.second-B)*(K-de[de.size()-2].first.first);
xc=(de[de.size()-2].first.second-B)*(K-de[de.size()-1].first.first);
if(zx<xc){
de.pop_back();
}else{
if(zx>xc) break;
if(de[de.size()-1].second<dp2[pr[ii]]){
break;
}else{
de.pop_back();
}
}
}
de.push_back({{K,B},dp2[pr[ii]]});
X=i;
while(de.size()>=2){
//if(de[0].first.first*X+de[0].first.second<=de[1].first.first*X+de[1].first.second) de.pop_front(); else break;
if(de[0].first.first*X+de[0].first.second<de[1].first.first*X+de[1].first.second){
de.pop_front();
}else{
if(de[0].first.first*X+de[0].first.second>de[1].first.first*X+de[1].first.second) break;
if(de[0].second>=de[1].second){
de.pop_front();
}else{
break;
}
}
}
if(bofx[i]==0){
dp[i]=dp[i-1];dp2[i]=dp2[i-1];
continue;
}
K=de[0].first.first;B=de[0].first.second;
X=i;
dp[i]=i*i-(K*X+B)+cost;dp2[i]=de[0].second+1;
}
//
return {dp[a],dp2[a]};
}
long long take_photos(int Nn, int Mm, int Kk, std::vector<int> Rr, std::vector<int> Cc) {
M=Nn;a=Mm;k=Kk;
dp.resize(a+3);dp2.resize(a+3);
/*for(i=0; i<a+3; i++){
dp[i].resize(min(k,a)+3);
dp2[i].resize(min(k,a)+3);
}*/
for(i=1; i<=M; i++){
if(Rr[i-1]>Cc[i-1]) swap(Rr[i-1],Cc[i-1]);
pp[i]={Rr[i-1]+1,-Cc[i-1]-1};
}
sort(pp+1,pp+M+1);
for(i=1; i<=M; i++) pp[i].second=-pp[i].second;
for(i=1; i<=M; i++){
if(pi!=0&&p[pi].second>=pp[i].second){
}else{
pi++;p[pi]=pp[i];
}
}
/*cout<<"rewrew "<<pi<<"\n";
for(i=1; i<=pi; i++) cout<<p[i].first<<" "<<p[i].second<<"\n";*/
for(i=1; i<=pi; i++){
pr[p[i].first]=p[i].second;
bofx[p[i].second]=p[i].first;
}
for(i=1; i<=a; i++){
pr[i]=max(pr[i],pr[i-1]);
}
P=DO(0);LEF1=P.first;LEF2=P.second;
//cout<<"0 0 0 "<<P.first<<" "<<P.second<<"\n\n";
if(P.second<=k){
return P.first;
}
lef=0;rig=a*a+1;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
P=DO(mid);
//cout<<lef<<" "<<rig<<" "<<mid<<" "<<P.first<<" "<<P.second<<"\n";
if(P.second<=k){
rig=mid;RIG1=P.first;RIG2=P.second;
}else{
lef=mid;LEF1=P.first;LEF2=P.second;
}
}
//
if(RIG2==k){
pas=RIG1-RIG2*rig;
}else{
pas=RIG1-k*rig;
}
return pas;
}
