#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
}
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int i, int j) {
if (r[i] != r[j]) {
return r[i] < r[j];
} else {
return c[i] > c[j];
}
});
vector<pair<int, int>> pts;
int mx = -1;
for (int id = 0; id < n; id++) {
int i = order[id];
if (c[i] <= mx) {
continue;
} else {
mx = max(mx, c[i]);
pts.emplace_back(r[i], c[i]);
}
}
n = (int) pts.size();
for (int i = 0; i < n; i++) {
r[i] = pts[i].first;
c[i] = pts[i].second;
}
vector<long long> w(n);
for (int i = 1; i < n; i++) {
long long d = c[i - 1] - r[i] + 1;
w[i] = max(0LL, d * d);
}
const long long inf = (long long) 1e18;
vector<long long> dp(n, inf);
for (int t = 0; t < k; t++) {
vector<long long> new_dp(n, inf);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= i; j++) {
long long d = c[i] - r[j] + 1;
long long ft = d * d;
if (j > 0) {
ft += dp[j - 1] - w[j];
}
new_dp[i] = min(new_dp[i], ft);
}
}
swap(dp, new_dp);
}
return dp[n - 1];
}
/*
5 7 2
0 3
4 4
4 6
4 5
4 6
*/
