#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],num[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,d=0;
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;
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=L[s].c+1;
while(e-s>1 && !is_ok(L[e-2],L[e-1],p)) e--;
L[e++]=p;
d=p.c;
}
return d;
}
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);
while(s<=e){
LL mid=(s+e)>>1;
x=CHT(mid);
if(x==k){
ans=dp[n]-k*mid;
break;
}else if(x<k){
e=mid-1;
ans=min(ans,dp[n]-x*mid);
}else{
s=mid+1;
}
}
return ans;
}
