#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 = 5e4 + 5;
const llint INF = 1e17;
vector<pair<int, int>> I, P;
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;
}
inline llint C(int i, int j) {
if (i == j) return 0LL;
int a = I[j].first, b = I[j].second;
int c = I[i + 1].first, d = I[i + 1].second;
int e = I[i].second;
return (llint)(b - c + 1) * (b - c + 1) -
(llint)max(0, e - c + 1) * max(0, e - c + 1);
}
void compute(int l, int r, int optl, int optr, vector<llint> &dp_prev,
vector<llint> &dp_curr) {
if (l > r) return;
int mid = (l + r) / 2;
pair<llint, int> best = {INF, -1};
for (int k = optl; k <= min(mid, optr); ++k)
best = min(best, {dp_prev[k] + C(k, mid), k});
dp_curr[mid] = best.first;
compute(l, mid - 1, optl, best.second, dp_prev, dp_curr);
compute(mid + 1, r, best.second, optr, dp_prev, dp_curr);
}
llint take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
I = get_intervals(n, r, c);
n = (int)I.size();
vector<llint> dp_prev(n, 0), dp_curr(n, 0);
for (int i = 0; i < n; ++i)
dp_prev[i] =
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1);
for (int i = 1; i < k; ++i) {
compute(0, n - 1, 0, n - 1, dp_prev, dp_curr);
swap(dp_prev, dp_curr);
}
return dp_prev[n - 1];
}
