#include <bits/stdc++.h>
#include "aliens.h"
#define int long long
using namespace std;
vector<vector<int>> mem;
int dp(vector<int> &a, int n, int i, int k){
if(mem[i][k] != -1) return mem[i][k];
if(i == n) return mem[i][k] = 0;
if(k == 0) return mem[i][k] = 1e18;
int ans = 1e18;
for(int j = i; j < n; j ++){
ans = min(ans, (a[j]-a[i]+1)*(a[j]-a[i]+1) + dp(a,n,j+1,k-1));
}
return mem[i][k] = ans;
}
int take_photos(signed n, signed m, signed k, vector<signed> r, vector<signed> c) {
if(n <= 50 && m <= 100 && k == n){
int ans = 0;
vector<vector<bool>> a(m,vector<bool>(m));
for(int i = 0; i < n; i ++){
int mi = min(r[i],c[i]);
int ma = max(r[i],c[i]);
for(int j = mi; j <= ma; j ++){
for(int k = mi; k <= ma; k ++){
if(!a[j][k]) ans ++;
a[j][k] = true;
}
}
}
return ans;
}else{
r.erase(unique(r.begin(), r.end()), r.end());
sort(r.begin(), r.end());
vector<int> rr(r.begin(), r.end());
n = rr.size();
mem = vector<vector<int>>(n+1,vector<int>(k+1,-1));
return dp(rr,n,0,k);
}
}
