#include<bits/stdc++.h>
#include "aliens.h"
#define MAX_N 100005
#define sq(x) ((x)*(x))
#define inf (1LL<<60)
using namespace std;
typedef long long LL;
typedef pair<LL,LL> pil;
struct node{
LL s,e;
}V[MAX_N];
struct line{
LL a,b,c;
}L[MAX_N];
LL n,k,ans;
LL dp[MAX_N],from[MAX_N];
bool is_ok(line a,line b,line c){
return (b.b-a.b)*(b.a-c.a)<(a.a-b.a)*(c.b-b.b);
}
LL CHT(LL c){
LL s,e;
LL i;
s=e=0;
L[e++]={-2*V[1].s,sq(V[1].s)-2*V[1].s,0};
for(i=1;i<=n;i++){
while(e-s>1 && L[s].a*V[i].e+L[s].b>=L[s+1].a*V[i].e+L[s+1].b) s++;
dp[i]=L[s].a*V[i].e+L[s].b+sq(V[i].e+1)+c;
from[i]=L[s].c;
line p={-2*V[i+1].s,sq(V[i+1].s)-2*V[i+1].s+dp[i]};
if(V[i].e-V[i+1].s+1>0) p.b-=sq(V[i].e-V[i+1].s+1);
p.c=i;
while(e-s>1 && !is_ok(L[e-2],L[e-1],p)) e--;
L[e++]=p;
}
for(c=0,i=n;i;i=from[i],c++);
return c;
}
long long take_photos(int N, int m, int K, std::vector<int> r, std::vector<int> c) {
LL i,s=0,e=(long long)m*m;
n=N;
k=K;
for(i=1;i<=n;i++){
V[i].s=min(r[i-1],c[i-1]);
V[i].e=max(r[i-1],c[i-1]);
}
sort(V+1,V+n+1,[&](const node x,const node y){return (x.s==y.s)?(x.e>y.e):(x.s<y.s);});
m=0;
LL x=-10000;
for(i=1;i<=n;i++){
if(x<V[i].e) V[++m]=V[i];
x=max(x,V[i].e);
}
n=m;
sort(V+1,V+n+1,[&](const node x,const node y){return x.e<y.e;});
ans=inf;
k=min(n,k);
bool Z=false;
LL lx=inf,lv,rx=-inf,rv;
while(s<=e){
LL mid=(s+e)>>1;
x=CHT(mid);
if(x==k){
return dp[n]-mid*x;
}else if(x<k){
rx=mid;rv=dp[n]-mid*x;
e=mid-1;
}else{
lx=mid;lv=dp[n]-mid*x;
s=mid+1;
}
}
return rv+(rv-lv)/(rx-lx)*(rx-k);
}
