#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll sq(int x) {
return (ll)x * x;
}
ll take_photos(int M, int N, int K, vector<int> R, vector<int> C) {
vector<vector<int>> v(N);
for (int i = 0; i < M; i++) {
v[max(R[i], C[i])].push_back(min(R[i], C[i]));
}
vector<pair<int, int>> h;
vector dp(N, vector<ll>(K + 1, 1e9));
for (int i = 0; i < N; i++) {
if (v[i].empty()) {
dp[i] = !i ? vector<ll>(K + 1, 0) : dp[i - 1];
continue;
}
for (int j : v[i]) h.emplace_back(j, i);
sort(h.begin(), h.end());
int t = -1;
for (auto [y, x] : h) {
for (int k = 1; k <= K; k++) {
if (t == -1) {
dp[i][k] = min(dp[i][k], sq(i - y + 1));
} else {
dp[i][k] = min(dp[i][k], dp[t][k - 1] + sq(i - y + 1) - (t < y ? 0 : sq(t - y + 1)));
}
}
t = max(t, x);
if (x == i) break;
}
}
return *min_element(dp[N - 1].begin(), dp[N - 1].end());
}
