#include "aliens.h"
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
long long squared(int x) {
return 1ll * x * x;
}
long long take_photos(int N, int M, int K, vector<int> R, vector<int> C) {
vector<pair<int, int> > A;
for (int i = 0; i < N; i++) {
int ri = R[i];
int ci = C[i];
if (ri > ci) swap(ri, ci);
A.push_back(make_pair(ci, ci - ri));
}
sort(A.begin(), A.end());
int j = 0;
for (auto p : A) {
while (j > 0 && p.second >= A[j - 1].second + p.first - A[j - 1].first) {
--j;
}
A[j++] = p;
}
A.resize(j);
N = j;
vector<long long> DP(N + 1, 0);
vector<long long> DP2(N + 1, 0);
for (int k = 0; k < K; k++) {
for (int i = 0; i < N; i++) {
if (i) {
DP[i] -= squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
}
DP2[i + 1] = squared(M);
for (int j = 0; j <= i; j++) {
DP2[i + 1] = min(
DP2[i + 1],
DP[j] + squared(1 + A[j].second + A[i].first - A[j].first)
);
}
}
DP.swap(DP2);
}
return DP[N];
}
