#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;
struct node{
LL x,y,i;
}V[MAX_N],line[MAX_N];
LL n,m,k,s,e;
LL dp[MAX_N],from[MAX_N];
bool is_delect(node x,node y,node z){return (x.x-z.x)*(y.y-x.y)>=(x.x-y.x)*(z.y-x.y)?true:false;}
void add(LL x,LL y,LL i){
while(e-s>1 && is_delect(line[e-2],line[e-1],{x,y})) e--;
line[e++]={x,y,i};
}
LL get_val(LL i,LL x){return line[i].x*x+line[i].y;}
LL is_ok(LL x){
LL i;
s=e=0;
add(-2*V[1].x,sq(V[1].x)-2*V[1].x,0);
for(i=1;i<=n;i++){
while(e-s>1 && get_val(s,V[i].y)>=get_val(s+1,V[i].y)) s++;
dp[i]=get_val(s,V[i].y)+sq(V[i].y+1)+x;
from[i]=line[s].i;
add(-2*V[i+1].x,sq(V[i+1].x)+dp[i]-2*V[i+1].x-sq(max(0LL,V[i].y-V[i+1].x+1)),i);
}
i=n;
LL c;
for(c=0;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,x,y;
n=N;
m=M;
k=K;
for(i=1;i<=n;i++) V[i]={min(r[i-1],c[i-1]),max(r[i-1],c[i-1])};
sort(V+1,V+n+1,[&](const node x,const node y){return (x.x==y.x)?x.y>y.y:x.x<y.x;});
m=n;n=0;
x=-inf;
for(i=1;i<=m;i++){
if(x>=V[i].y) continue;
V[++n]=V[i];
x=V[i].y;
}
LL l,rr;
l=0;
rr=sq((LL)M);
k=min(k,n);
LL mid,ans=0;
while(l<=rr){
mid=(l+rr)>>1;
x=is_ok(mid);
if(x==k) return dp[n]-k*mid;
if(x<k){rr=mid-1; ans=max(ans,dp[n]-x*mid);}
else{
l=mid+1;
}
}
return ans;
}
