unsigned X=12345;
int rand_(){return(X*=3)>>1;}
int(*compar)(int,int);
void sort_(int*aa,int l,int r)
{
while(l<r)
{
int i=l,j=l,k=r,t,p=aa[l+rand_()%(r-l)];
while(j<k)
switch(compar(aa[j],p))
{
case 0:++j;break;
case -1:t=aa[i],aa[i]=aa[j],aa[j]=t,++i,++j;break;
case 1:t=aa[--k],aa[k]=aa[j],aa[j]=t;break;
}
sort_(aa,l,i);
l=k;
}
}
#include "aliens_c.h"
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long long lo(long long a,long long b){return a<b?a:b;}
typedef struct { long long m, c; } line;
#define N 1000000
int n,m,k,r[N],c[N];
long long dp[N],ans;
int*r0,*c0,real_n;
int comparpoint0(int i,int j)
{
if(r0[i]==r0[j])return c0[i]>c0[j]?-1:c0[i]<c0[j]?1:0;
return r0[i]<r0[j]?-1:r0[i]>r0[j]?1:0;
}
void filter_covered()
{
static int o[100002]={0},t[1000002]={0};
for(int i=0;i<n;++i)o[i]=i;
compar=comparpoint0;
sort_(o,0,n);
for(int i=0;i<n;++i)
{
int j=o[i];
int cver=0;
for(int p=c0[j];p<sizeof t/sizeof*t;p+=p&-p) cver+=t[p];
for(int p=c0[j];p;p-=p&-p) ++t[p];
if(!cver) r[real_n]=r0[j],c[real_n]=c0[j],++real_n;
}
n=real_n;
}
line cht[N<<1];
int head,tail;
long long intersectx(line a,line b)
{
return (b.c-a.c)/(a.m-b.m);
}
void chtadd(line k)
{
while(head-tail>1&&intersectx(k,cht[head-1])>intersectx(k,cht[head-2]))--head;
cht[head++]=k;
}
line chtqry(long long x)
{
while(head-tail>1&&intersectx(cht[tail],cht[tail+1])<x)++tail;
return cht[tail];
}
#define ASSERT(x) if (!(x)) __builtin_trap()
long long what(long long lambda,int*count)
{
head=tail=0;
static long long dp[N];
memset(dp,0,sizeof dp);
long long pref=0;
int zz=0;
for(int i=0;i<n;++i)
{
long long st=r[i]-1;
line nw={-2*st,st*st+lambda+pref};
chtadd(nw);
line best=chtqry(c[i]);
dp[i]=best.m*c[i]+best.c+1ll*c[i]*c[i];
//printf(" (%d) [%d %d] : (%lld %lld\n",i,r[i],c[i],best.m,best.c);
if(i)
{
ASSERT(r[i]>r[i-1]);
ASSERT(c[i]>c[i-1]);
}
if(best.m==nw.m&&best.c==nw.c)
++zz;
pref+=dp[i];
//printf(" = %lld\n",dp[i]);
}
*count=zz;
return dp[n-1];
}
long long take_photos(int n0, int m0, int k0, int* r00, int* c00)
{
n=n0,m=m0,k=k0;
/* preprocess point - turn to 1-indexed, turn to right diagonal */
for(int i=0;i<n;++i)
{
++r00[i],++c00[i];
if(r00[i]>c00[i]){int tt=r00[i];r00[i]=c00[i];c00[i]=tt;}
}
r0=r00,c0=c00;
filter_covered();
long long l=0,r=1e12;
while(l<=r)
{
long long o=l+(r-l)/2;
int count;
long long dp=what(o,&count);
if(count<=k)
ans=dp-o*count,l=o+1;
else r=o-1;
}
return ans;
}
