#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int maxn = 5e2 + 2;
int dp[maxn][maxn]; // dp[i][j] -> numarul minim de celule pentru a putea fotografia primele j puncte de interes folosind i fotografii
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
if (k == n) {
int a[m + 1][m + 1] = {};
int rs = 0;
for (int i = 0; i < n; i++){
for (int j = min(r[i], c[i]); j <= max(r[i], c[i]); j++){
for (int k = min(r[i], c[i]); k <= max(r[i], c[i]); k++){
if (!a[j][k]) rs++;
a[j][k] = 1;
}
}
}
return rs;
}
for (int i = 0; i < maxn; i++){
for (int j = 0; j < maxn; j++){
dp[i][j] = 1e8;
}
}
vector <pair <int, int> > v;
sort(r.begin(), r.end());
for (int i = 0; i < n; i++) dp[1][i] = (r[i] - r[0] + 1) * (r[i] - r[0] + 1);
for (int i = 2; i <= k; i++){
for (int j = 1; j < n; j++){
for (int k = j; k > 0; k--){
dp[i][j] = min(dp[i][j], dp[i-1][k-1] + ((r[j] - r[k] + 1) * (r[j] - r[k] + 1)));
}
}
}
int rs = 1e9;
for (int i = 1; i <= k; i++){
rs = min(rs, dp[i][n-1]);
}
return rs;
}
