#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
#define all(v) v.begin(),v.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<60;
void chmin(ll &a,ll b){a=min(a,b);}
struct T{
ll a,b;
};
struct CHT{
int n;
vector<T> dat;
vector<ll> xs;
CHT(vector<ll>& a){
n=1;
while(n<a.size())n<<=1;
xs=a;
int c=0;
while(xs.size()<=n){
xs.eb(10000000+c);
c++;
}
dat.resize(2*n,T{0,INF});
}
inline ll f(T& a,ll x){
return a.a*x+a.b;
}
void upd(T a,int k,int l,int r){
int m=(l+r)/2;
ll vl=f(dat[k],xs[l]),vr=f(dat[k],xs[r-1]),vl2=f(a,xs[l]),vr2=f(a,xs[r-1]);
if(vl<=vl2&&vr<=vr2)return;
if(vl2<=vl&&vr2<=vr){
dat[k]=a;
return;
}
if(r-l<=1)return;
if(vl2<=vl)swap(dat[k],a);
ll vm=f(dat[k],xs[m]),vm2=f(a,xs[m]);
if(vm>vm2){
swap(dat[k],a);
upd(a,k<<1,l,m);
}else{
upd(a,k<<1|1,m,r);
}
}
inline void upd(T a){upd(a,1,0,n);}
ll get(ll x){
int k=lower_bound(all(xs),x)-xs.begin();
k+=n;
ll res=f(dat[k],x);
k>>=1;
while(k>0){
chmin(res,f(dat[k],x));
k>>=1;
}
return res;
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<int> cs(m,-1);
for(int i=0;i<n;i++){
if(r[i]>c[i]){
swap(r[i],c[i]);
}
cs[r[i]]=max(cs[r[i]],c[i]);
}
vector<ll> a,b,bs;
int ma=-1;
for(int i=0;i<m;i++){
if(cs[i]>ma){
a.eb(i-1);
b.eb(cs[i]);
bs.eb(cs[i]);
ma=cs[i];
}
}
sort(all(bs));
bs.erase(unique(all(bs)),bs.end());
n=a.size();
vector<vector<ll>> dp(k+1,vector<ll>(n+1,INF));
dp[0][0]=0;
for(int i=0;i<k;i++){
CHT cht(bs);
for(int j=0;j<n;j++){
ll t=dp[i][j]+a[j]*a[j];
if(j>0&&b[j-1]>=a[j]+1){
t-=(b[j-1]-a[j])*(b[j-1]-a[j]);
}
cht.upd(T{-2LL*a[j],t});
dp[i+1][j+1]=cht.get(b[j])+b[j]*b[j];
chmin(dp[i+1][j+1],dp[i][j+1]);
}
}
return dp[k][n];
}
