#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;
long long INF = squared(M + 1);
vector<long long> DP(N + 1, INF);
DP[0] = 0;
for (int k = 0; k < K; k++) {
for (int i = 1; i < N; i++) {
DP[i] -= squared(max(0, 1 + A[i].second - A[i].first + A[i - 1].first));
}
for (int i = N; i > 0; i--) {
DP[i] = INF;
for (int j = 0; j < i; j++) {
DP[i] = min(
DP[i],
DP[j] + squared(1 + A[j].second + A[i - 1].first - A[j].first)
);
}
}
}
return DP[N];
}
