#include "aliens.h"
#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define sq(k) (k)*(k)
typedef long long ll;
using namespace std;
ll VL[100100],rev[100100];
pair<ll,int>dp[100100];
struct seg{
ll k,b,cnt;
inline pair<ll,int> operator()(int x){
return {k*x+b,cnt};
}
seg(){k=0,b=1e18,cnt=0;}
seg(ll k_,ll b_,ll cnt_){k=k_,b=b_,cnt=cnt_;}
};
struct link_cut_tree{
seg T[1<<20];
int lc[1<<20];
int rc[1<<20];
int CC;
int rt;
void upd(int &i,int l,int r,seg SG){
if(!i)return void(T[i=++CC]=SG);
if(l==r-1) {
if(T[i](l)>SG(l))
swap(T[i],SG);
return;
}
if(T[i].k>SG.k)swap(T[i],SG);
if(T[i](l+r>>1)<SG(l+r>>1))
return upd(lc[i],l,l+r>>1,SG);
swap(T[i],SG),upd(rc[i],l+r>>1,r,SG);
}
pair<ll,int> qry(int i,int l,int r,int p){
if(!i) return {(ll)1e18,0};
if(l==r-1)return T[i](p);
if(l+r>>1<=p)
return min(T[i](p),qry(rc[i],l+r>>1,r,p));
return min(T[i](p),qry(lc[i],l,l+r>>1,p));
}
void reset(){
rt=0;
for(int i=1;i<=CC;i++)
lc[i]=rc[i]=0;
CC=0;
}
inline void addline(ll cnt,ll k,ll b){
upd(rt,1,1e6+1,seg(k,b,cnt));
}
inline pair<ll,int>querypos(int pos){
return qry(rt,1,1e6+1,pos);
}
link_cut_tree(){rt=CC=0;memset(lc,0,sizeof lc);memset(rc,0,sizeof rc);}
} LCT;
ll whttoad(int i){
if(rev[i]>=VL[i+1])
return sq(rev[i]-VL[i+1]+1);
return 0;
}
int dodp(ll pen,int n){
LCT.reset();
LCT.addline(0,-2*VL[1]+2,sq(VL[1]-1));
for(int i=1;i<=n;i++) {
dp[i]=LCT.querypos(rev[i]);
dp[i].second++;
dp[i].first+=pen+sq(rev[i]);
LCT.addline(dp[i].second,-2*VL[i+1]+2,sq(VL[i+1]-1)+dp[i].first-whttoad(i));
}
return dp[n].second;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
ll MXX=m;
swap(m,n);
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!=mp2.begin());
for(auto i:todie)
mp.erase(i),mp2.erase(i);
for(auto&[i,j]:mp)
rev[j=++CC]=i,VL[j]=mp2[i];
n=mp.size();
ll L=0,R=MXX*MXX,res=0;
while(L<=R){
ll mid=L+R>>1;
if(dodp(mid,n)<=k)
R=mid-1,res=mid;
else L=mid+1;
}
dodp(res,n);
return dp[n].first-res*k;
}
