#include "aliens.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int maxn=4005;
bool cmp(pair < int, int > a, pair < int, int > b){
return max(a.first, a.second)<max(b.first, b.second);
}
int n, m, k;
ll dp[maxn][maxn];
pair < int, int > p[maxn];
ll pov[maxn][maxn];
void precompute(){
int maxx, maxy;
int minx, miny;
int raz;
for(int i=0; i<n; i++){
maxx=0;
maxy=0;
minx=1e9;
miny=1e9;
for(int j=i; j<n; j++){
maxx=max(maxx, p[j].first);
minx=min(minx, p[j].first);
maxy=max(maxy, p[j].second);
miny=min(miny, p[j].second);
raz=abs(max(maxx, maxy)-min(minx, miny))+1;
pov[i][j]=(ll)raz*raz;
}
}
}
ll take_photos(int nn, int mm, int kk, vector < int > r, vector < int > c){
n=nn;
m=mm;
k=kk;
for(int i=0; i<n; i++){
if(r[i]<c[i]){
swap(r[i], c[i]);
}
p[i]={r[i], c[i]};
}
sort(p, p+n);
/* for(int i=0; i<n; i++){
cout << p[i].first << ' ' << p[i].second << endl;
}*/
precompute();
/* for(int i=0; i<n; i++){
for(int j=i; j<n; j++){
cout << pov[i][j] << ' ';
}
cout << endl;
}*/
for(int i=0; i<n; i++){
dp[i][1]=pov[0][i];
for(int j=2; j<=k; j++){
dp[i][j]=1e18;
for(int l=0; l<i; l++){
dp[i][j]=min(dp[i][j], dp[l][j-1]+pov[l+1][i]);
}
}
}
ll sol=1e18;
for(int i=1; i<=k; i++){
sol=min(sol, dp[n-1][i]);
}
return sol;
}
