#include "aliens.h"
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int stb[50100][17],rev[50100];
inline int 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){
int k=stbqr(l+1,r);
ll A=(rev[r]-k+1);
ll B=max(0,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++){
int 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);
for(int i=1;i<=n;i++)
for(int k=0;k<17;k++)
stb[i][k]=i+1;
map<int,int>mp;
int CC=0;
for(int i=0;i<m;i++){
r[i]++;c[i]++;
if(r[i]>c[i]) swap(r[i],c[i]);
mp[c[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],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),memcpy(dp,dp2,sizeof dp);
return dp[n];
}
