#include "aliens.h"
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define chkmin(a, b) a = min(a, b)
#define chkmax(a, b) a = max(a, b)
#define int ll
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
const int MAX_N = 5001;
const ll infinity = 1e18;
ll dp[MAX_N][MAX_N];
int ind[MAX_N];
int prefix_max[MAX_N];
bitset<MAX_N> inside;
long long take_photos(int32_t n, int32_t m, int32_t k, std::vector<int32_t> r, std::vector<int32_t> c) {
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) swap(r[i], c[i]);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) continue;
if (r[j] < r[i] && c[j] > c[i]) {
inside[i] = true;
r[i] = m + 1, c[i] = m + 1;
break;
}
}
}
iota(ind, ind + n, 0);
sort(ind, ind + n, [&] (int i, int j) {
return r[i] + c[i] < r[j] + c[j];
});
n -= inside.count();
for (int i = 0; i < n; i++) {
prefix_max[i + 1] = max<ll>(prefix_max[i], c[ind[i]] + 1);
}
fill(dp[0], dp[0] + n, infinity);
for (int j = 1; j <= k; j++) {
for (int i = 0; i < n; i++) {
dp[j][i] = infinity;
int left = m, right = 0;
for (int l = i; l >= 0; l--) {
chkmin(left, ll(r[ind[l]]));
chkmax(right, ll(c[ind[l]] + 1));
ll x = (l ? dp[j - 1][l - 1] : 0) + ll(right - left) * (right - left);
if (prefix_max[l] > left) {
x -= (prefix_max[l] - left) * (prefix_max[l] - left);
}
chkmin(dp[j][i], x);
}
}
}
return dp[k][n - 1];
}
//6 7 2
//0 3
//4 4
//4 6
//4 5
//4 6
//0 5
