#include "aliens.h"
#include <bits/stdc++.h>
#define eb emplace_back
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);}
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;
int ma=-1;
for(int i=0;i<m;i++){
if(cs[i]>ma){
a.eb(i-1);
b.eb(cs[i]);
ma=cs[i];
}
}
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++){
vector<ll> t(n+1);
for(int j=0;j<n;j++){
t[j]=dp[i][j]+a[j]*a[j];
if(j>0&&b[j-1]>=a[j]+1){
t[j]-=(b[j-1]-a[j])*(b[j-1]-a[j]);
}
}
for(int j=0;j<n;j++){
for(int l=0;l<=j;l++){
chmin(dp[i+1][j+1],-2LL*a[l]*b[j]+t[l]+b[j]*b[j]);
}
chmin(dp[i+1][j+1],dp[i][j+1]);
}
}
return dp[k][n];
}
