#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
const long long INF = 1e18;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i = 0;i<n;i++) {
if(c[i] < r[i]) {
swap(c[i], r[i]);
}
}
map<int,int> mp;
for(int i = 0;i<n;i++) {
mp[r[i]] = max(mp[r[i]], c[i]);
}
vector<pair<int,int>> pts;
for(auto i:mp) {
pair<int,int> p = i;
pts.push_back(p);
}
// for(auto i:pts) {
// cout << "(" << i.first << " " << i.second << ")" << "\n";
// }
n = pts.size();
long long dp[n+1][k+1];
for(int i = 0;i<=k;i++)dp[0][i] = 0;
for(int j = 1;j<=n;j++)dp[j][0] = INF;
for(int i = 1;i<=n;i++) {
for(int j = 1;j<=k;j++) {
dp[i][j] = INF;
long long mx = (pts[i-1].second-pts[i-1].first+1);
for(int t = i;t>=1;t--) {
mx = max((long long)pts[i-1].second-pts[t-1].first+1, mx);
dp[i][j] = min(dp[i][j], dp[t-1][j-1]+mx*mx);
}
}
}
return dp[n][k];
}
