#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,dp[1000009],dp2[1000009],lef,rig,mid,A,B,C,X,za,z,zz;
long long bofx[1000009],BOFX[1000009];
pair <long long, long long> p[1000009],pp[1000009];
pair <pair <long long, long long>, long long> seg[4000009];
vector <long long> V[1000009];
bool fun(pair <pair <long long, long long>, long long> q, pair <pair <long long, long long>, long long> w, long long rr){
long long qw=q.first.first*rr+q.first.second,we=w.first.first*rr+w.first.second;
if(qw<we) return 0;
if(qw>we) return 1;
if(q.second>w.second) return 1;
return 0;
}
void upd(long long q, long long w, long long rr){
if(q>w) return;
if(seg[rr].second==-1){
seg[rr]={{A,B},C};
return;
}
long long mid=(q+w)/2;
if(fun(seg[rr],{{A,B},C},mid)){
swap(seg[rr].first.first,A);swap(seg[rr].first.second,B);swap(seg[rr].second,C);
}
if(fun(seg[rr],{{A,B},C},q)){
upd(q,mid-1,rr*2);
}else{
if(fun(seg[rr],{{A,B},C},w)){
upd(mid+1,w,rr*2+1);
}
}
}
void read(long long q, long long w, long long rr){
if(q>w) return;
if(seg[rr].second==-1){
return;
}
long long qw=seg[rr].first.first*X+seg[rr].first.second;
if(qw<z||(qw==z&&seg[rr].second<zz)){
z=qw;zz=seg[rr].second;
}
long long mid=(q+w)/2;
if(X<mid){
read(q,mid-1,rr*2);
}
if(X>mid){
read(mid+1,w,rr*2+1);
}
}
pair <long long, long long> fun(){
for(i=0; i<=a+1; i++){
dp[i]=a*a+mid*(a+2)+3;dp2[i]=0;
}
za=1;
while(za<a) za*=2;
for(i=0; i<=za*2+2; i++){
seg[i]={{-1,-1},-1};
}
dp[0]=0;dp2[0]=0;
for(i=1; i<=a; i++){
for(vector <long long>::iterator it=V[i-1].begin(); it!=V[i-1].end(); it++){
ii=(*it);
if(pr[ii]>ii){
A=-2*ii;B=ii*ii+dp[pr[ii]]-(pr[ii]-ii)*(pr[ii]-ii);C=dp2[pr[ii]];
upd(1,za,1);
}else{
A=-2*ii;B=ii*ii+dp[pr[ii]];C=dp2[pr[ii]];
upd(1,za,1);
}
}
if(bofx[i]==0){
dp[i]=dp[i-1];dp2[i]=dp2[i-1];
continue;
}
dp[i]=i*i+mid;dp2[i]=1;
X=i;z=zz=999999999999999999LL;
read(1,za,1);
z+=i*i+mid;zz++;
if(dp[i]>z||(dp[i]==z&&dp2[i]>zz)){
dp[i]=z;dp2[i]=zz;
}
}
return make_pair(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;pas=a*a+4;
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];
}
}
for(i=1; i<=pi; i++){
pr[p[i].first]=p[i].second;BOFX[p[i].first]=1;
bofx[p[i].second]=p[i].first;
}
for(i=1; i<=a; i++){
pr[i]=max(pr[i],pr[i-1]);
}
for(i=0; i<=a; i++){
if(BOFX[i+1]==0) continue;
V[pr[i]].push_back(i);
}
pair <long long, long long> P;
mid=0;
P=fun();
if(P.second<=K){
return P.first;
}
lef=0;rig=a*a+4;
long long EF=0,KL;
while(1){
if(lef+1>=rig) break;
mid=(lef+rig)/2;
P=fun();
if(P.second<=K){
pas=min(pas,P.first-mid*P.second);
rig=mid;KL=P.first-mid*K;EF=P.second;
}else{
lef=mid;
}
}
if(EF<K){
return KL;
}
return pas;
}
