#include "aliens.h"
#include <bits/stdc++.h>
#ifdef LOCAL
#include "../../codebook/debug.h"
#else
#define debug(...) 0516
#endif
using namespace std;
long long solve_1(int n, int m, int k, vector<int> &r, vector<int> &c) {
vector<vector<bool>> g(m, vector<bool>(m));
long long ans = 0;
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
for (int x = r[i]; x <= c[i]; x++) {
for (int y = r[i]; y <= c[i]; y++) {
if (g[x][y] == false) {
g[x][y] = true;
ans += 1;
}
}
}
}
return ans;
}
long long solve_2(int n, int m, int k, vector<int> &r, vector<int> &c) {
sort(c.begin(), c.end());
c.erase(unique(c.begin(), c.end()), c.end());
n = c.size();
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++) {
dp[i].assign(k + 1, m * m);
for (int j = 1; j <= k; j++) {
for (int t = 0; t <= i - 1; t++) {
dp[i][j] = min(dp[i][j], dp[t][j - 1] +
(c[i - 1] - c[t] + 1) * (c[i - 1] - c[t] + 1));
}
}
}
debug(dp);
return dp[n][k];
}
void clean(int &n, 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) {
return make_pair(r[i], -c[i]) < make_pair(r[j], -c[j]);
});
vector<int> new_r, new_c;
for (int i = 0; i < n; i++) {
if (new_r.empty() || c[order[i]] > new_c.back()) {
new_r.push_back(r[order[i]]);
new_c.push_back(c[order[i]]);
}
}
r = new_r;
c = new_c;
n = r.size();
}
long long solve_3(int n, int m, int k, vector<int> &r, vector<int> &c) {
clean(n, r, c);
debug(r);
debug(c);
// cost cover [i...j] and remove overlapping
auto cost = [&](int i, int j) {
int res = (c[j] - r[i] + 1) * (c[j] - r[i] + 1);
if (i != 0) {
int d = max(0, c[i - 1] - r[i] + 1);
res -= d * d;
}
return res;
};
vector<vector<int>> dp(n + 1, vector<int>(k + 1));
for (int i = 1; i <= n; i++) {
dp[i].assign(k + 1, m * m);
for (int j = 1; j <= k; j++) {
for (int t = 1; t <= i; t++) {
dp[i][j] = min(dp[i][j], dp[i - t][j - 1] + cost(i - t, i - 1));
}
}
}
debug(dp);
return dp[n][k];
}
long long solve_4(int n, int m, int k, vector<int> &r, vector<int> &c) {
clean(n, r, c);
debug(r);
debug(c);
// cost cover [i...j] and remove overlapping
auto cost = [&](int i, int j) {
long long res = 1LL * (c[j] - r[i] + 1) * (c[j] - r[i] + 1);
if (i != 0) {
long long d = max(0, c[i - 1] - r[i] + 1);
res -= d * d;
}
return res;
};
vector<vector<long long>> dp(k + 1, vector<long long>(n + 1));
vector<vector<int>> opt(k + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
dp[1][i] = cost(0, i - 1);
}
for (int i = 2; i <= k; i++) {
for (int j = n; j > 0; j--) {
dp[i][j] = dp[i - 1][j];
int upper = j == n ? n - 1 : min(j - 1, opt[i][j + 1]);
for (int t = opt[i - 1][j]; t <= upper; t++) {
if (dp[i][j] > dp[i - 1][t] + cost(t, j - 1)) {
dp[i][j] = dp[i - 1][t] + cost(t, j - 1);
opt[i][j] = t;
}
}
}
}
debug(dp);
return dp[k][n];
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
// if (n <= 50 && m <= 100 && k == n) return solve_1(n, m, k, r, c);
// if (n <= 500 && m <= 1000 && r == c) return solve_2(n, m, k, r, c);
// if (n <= 500 && m <= 1000) return solve_3(n, m, k, r, c);
if (n <= 4000) return solve_4(n, m, k, r, c);
return 0;
}
