#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxk=100+10;
long long dp[maxn][maxk],n,m,k,cost[maxn],inf=1e14;
struct cht{
long long inersect(pair<long long ,long long>a,pair<long long ,long long>b){
long long sor=a.first-b.first,makh=b.second-a.second;
if(makh==0){
if(sor>0){
return -inf;
}
return inf;
}
if(makh<0){
sor*=-1;
makh*=-1;
}
if(sor<0){
return sor/makh;
}
return (sor+makh-1)/makh;
}
vector<pair<long long ,pair<long long ,long long>>>st;
void clear(){
st.clear();
}
void ins(pair<long long,long long>a){
while((int)st.size()>0){
long long x=inersect(a,st.back().second);
if(x<=st.back().first){
st.pop_back();
continue;
}
st.push_back(make_pair(x,a));
return ;
}
st.push_back(make_pair(-inf,a));
}
long long pors(long long x){
if(st.size()==0){
return -inf;
}
int p=lower_bound(st.begin(),st.end(),make_pair(x+1,make_pair(-inf,-inf)))-st.begin();
p--;
return st[p].second.first+x*st[p].second.second;
}
}cht;
long long take_photos(int n_, int m_, int k_, std::vector<int> r, std::vector<int> c) {
n=n_;
m=m_;
k=k_;
vector<pair<long long,long long>>allv;
allv.resize(n);
for(int i=0;i<n;i++){
allv[i]=make_pair(r[i],c[i]);
if(allv[i].first>allv[i].second){
swap(allv[i].first,allv[i].second);
}
allv[i].second=-allv[i].second;
}
sort(allv.begin(),allv.end());
vector<pair<long long,long long>>fake;
for(int i=0;i<n;i++){
allv[i].second*=-1;
if(i==0||fake.back().second-(allv[i].first-fake.back().first)<allv[i].second){
fake.push_back(allv[i]);
}
}
allv=fake;
n=(int)fake.size();
for(int i=0;i<=n;i++){
dp[i][0]=inf;
}
for(int i=1;i<n;i++){
long long c=max(-1ll,allv[i-1].second-allv[i].first);
c++;
c*=c;
cost[i]=c;
}
// dp[0][0]=(allv[0].second-allv[0].first+1)*(allv[0].second-allv[0].first+1);
for(int lev=1;lev<=k;lev++){
cht.clear();
dp[0][lev]=inf;
vector<vector<int>>addy(n+1);
for(int i=0;i<n;i++){
if(i>0){
//int p=lower_bound(allv.begin(),allv.end(),make_pair(allv[i].second,-1ll))-allv.begin();
int p=i+1;
if(allv[i].first==allv[i].second){
p=i;
}
addy[p].push_back(i);
}
for(auto x:addy[i]){
cht.ins(make_pair(-dp[x-1][lev-1]+cost[x]-(allv[x].first-1)*(allv[x].first-1),allv[x].first-1));
}
dp[i][lev]=cht.pors(2*allv[i].second)-allv[i].second*allv[i].second;
dp[i][lev]=-dp[i][lev];
// cout<<i<<" "<<lev<<" "<<dp[i][lev]<<endl;
if(dp[i][lev]>=inf){
dp[i][lev]=min(dp[i][lev],1ll*(allv[i].second-allv[0].first+1)*(allv[i].second-allv[0].first+1));
}
// cout<<i<<" "<<lev<<" "<<dp[i][lev]<<endl;
}
for(auto x:addy[n]){
cht.ins(make_pair(-dp[x-1][k-1]+cost[x]-(allv[x].first-1)*(allv[x].first-1),allv[x].first-1));
}
}
long long te=allv[n-1].second;
long long mainres=cht.pors(2*allv[n-1].second)-(te*te);
mainres=-mainres;
if(mainres>=inf){
mainres=1ll*(te-(allv[0].first)+1)*(te-(allv[0].first)+1);
}
return mainres;
}
