#include "aliens.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
ll stb[50100][17],rev[50100];
inline ll stbqr(int a,int b){
int x=31-__builtin_clz(b-a);
return min(stb[a][x],stb[b-(1<<x)+1][x]);
}
inline ll Gcost(int l,int r){
ll k=stbqr(l+1,r);
ll A=max(0ll,rev[r]-k+1);
ll B=max(0ll,rev[l]-k+1);
return A*A-B*B;
}
ll dp[50100],dp2[50100];
void dnc(int l,int r,int opl,int opr){
if(l>r)return;
int mid=l+r>>1,opt=0;
dp2[mid]=1e18;
for(int i=opl;i<mid&&i<=opr;i++){
ll K=Gcost(i,mid)+dp[i];
if(K<dp2[mid])dp2[mid]=K,opt=i;
}
dnc(l,mid-1,opl,opt);
dnc(mid+1,r,opt,opr);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
swap(m,n);
memset(stb,1,sizeof stb);
map<int,int>mp;
int CC=0;
map<int,int>mp2;
for(int i=0;i<m;i++){
r[i]++;c[i]++;
if(r[i]>c[i]) swap(r[i],c[i]);
mp[c[i]];
if(mp2.count(c[i]))
mp2[c[i]]=min(mp2[c[i]],r[i]);
else mp2[c[i]]=r[i];
}
vector<int>todie;
int sfc=1e9;
auto it=mp2.end();
do {
it--;
if(it->second>=sfc)
todie.push_back(it->first);
else sfc=it->second;
}while(it!=mp.begin());
for(auto i:todie)
mp.erase(i),mp2.erase(i);
for(auto&[i,j]:mp)
rev[j=++CC]=i;
n=mp.size();
for(int i=0;i<m;i++)
stb[mp[c[i]]][0]=min(stb[c[i]][0],(ll)r[i]);
for(int i=1;i<17;i++)
for(int j=1;j+(1<<i)<=n+2;j++)
stb[j][i]=min(stb[j][i-1],stb[j+(1<<i-1)][i-1]);
memset(dp,1,sizeof dp);
dp[0]=0;
while(k--){
dnc(1,n,0,n);
for(int i=1;i<=n;i++)
dp[i]=dp2[i];
}
return dp[n];
}
