#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);
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++){
for(int j=0;j<n;j++){
for(int l=0;l<=j;l++){
ll d=(b[j]-a[l]+1LL)*(b[j]-a[l]+1LL);
if(l>0&&b[l-1]>=a[l]){
d-=(b[l-1]-a[l]+1LL)*(b[l-1]-a[l]+1LL);
}
chmin(dp[i+1][j+1],dp[i][l]+d);
}
chmin(dp[i+1][j+1],dp[i][j+1]);
}
}
return dp[k][n];
}
