#include <vector>
#include <string>
#include <set>
#include <algorithm>
#include <iostream>
#include <utility>
#include "aliens.h"
using namespace std;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
if (k == n && m <= 100){
int total = 0;
for (int i = 0; i < m; i++){
for (int j = 0; j < m; j++){
bool good = false;
for (int a = 0; a < n; a++){
if (i <= max(r[a], c[a]) && j <= max(r[a], c[a]) && i >= min(r[a], c[a]) && j >= min(r[a], c[a])){
good = true;
}
}
if (good){
total++;
}
}
}
return total;
}
bool is_central = true;
for (int i = 0; i < n; i++){
if (r[i] != c[i]){
is_central = false;
}
}
if (is_central && n <= 500 && m <= 1000){
vector<int> locations;
for (int i = 0; i < n; i++){
if (find(locations.begin(), locations.end(), r[i]) == locations.end()){
locations.push_back(r[i]);
}
}
sort(locations.begin(), locations.end());
n = locations.size();
vector<vector<int> > DPnk (n, vector<int> (k + 1, m * m));
for (int N = 0; N < n; N++){
for (int K = 1; K <= k; K++){
DPnk[N][K] = (locations[N] - locations[0] + 1) * (locations[N] - locations[0] + 1);
for (int n1 = 1; n1 <= N; n1++){
DPnk[N][K] = min(DPnk[N][K], DPnk[n1 - 1][K - 1] + (locations[N] - locations[n1] + 1) * (locations[N] - locations[n1] + 1));
}
}
}
return DPnk[n - 1][k];
}
return -5;
}
