#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
using llint = long long;
const int MAXN = 505;
const int MAXM = 1005;
const llint INF = 1e17;
llint dp[MAXN][MAXN];
struct Event {
int x, type, id;
Event() {}
Event(int x, int type, int id) : x(x), type(type), id(id) {}
friend bool operator<(const Event &A, const Event &B) {
if (A.x == B.x) return A.type < B.type;
return A.x < B.x;
}
};
vector<pair<int, int>> get_intervals(int n, const vector<int> &r,
const vector<int> &c) {
vector<Event> e;
for (int i = 0; i < n; ++i) {
int lo = min(r[i], c[i]);
int hi = max(r[i], c[i]);
e.emplace_back(lo, 0, i);
e.emplace_back(hi, 1, i);
}
sort(e.begin(), e.end());
multiset<int> ms;
vector<pair<int, int>> ret;
for (const auto &p : e) {
if (p.type == 0) {
ms.insert(p.x);
continue;
}
int lo = min(r[p.id], c[p.id]);
ms.erase(ms.find(lo));
if (ms.empty() || *ms.begin() > lo) ret.emplace_back(lo, p.x);
}
return ret;
}
llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
auto I = get_intervals(n, r, c);
n = (int)I.size();
for (int i = 1; i <= n; ++i) dp[i][0] = INF;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= k; ++j) {
int a = I[i - 1].first, b = I[i - 1].second;
dp[i][j] = (llint)(b - I[0].first + 1) * (b - I[0].first + 1);
for (int ii = 1; ii <= i; ++ii) {
int c = I[ii - 1].first, d = I[ii - 1].second;
dp[i][j] =
min(dp[i][j], dp[ii][j - 1] + (llint)(b - a + 1) * (b - a + 1) -
(llint)max(0, d - a + 1) * max(0, d - a + 1));
}
}
}
return dp[n][k];
}
