#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define TRACE(x) cerr << #x << " " << x << endl
#define _ << " " <<
using llint = long long;
const llint INF = 1e15;
int n, m, k;
vector<pair<int, int>> I, P;
vector<llint> A, B;
vector<int> hull;
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 ccw(int i, int j, int k) {
return A[i] * (B[j] - B[k]) + A[j] * (B[k] - B[i]) + A[k] * (B[i] - B[j]);
}
void insert(int x, int *t) {
while (hull.size() >= 2 && ccw(hull[hull.size() - 2], hull.back(), x) > 0)
hull.pop_back();
hull.push_back(x);
if (*t >= (int)hull.size()) *t = (int)hull.size() - 1;
}
pair<llint, int> dp(llint cost) {
vector<llint> f(n, 0);
vector<int> cnt(n, 0);
hull.clear();
A.resize(n, 0); B.resize(n, 0);
int t = 0;
for (int i = 0; i < n; ++i) {
llint c = (llint) I[i].second * I[i].second + cost;
llint x = (llint) I[i].second;
f[i] = INF;
cnt[i] = -1;
for (; t < (int) hull.size(); ++t) {
llint a = A[hull[t]], b = B[hull[t]];
if (c + a * x + b > f[i]) { --t; break; }
if (c + a * x + b == f[i]) {
cnt[i] = min(cnt[i], cnt[hull[t]] + 1);
} else {
f[i] = c + a * x + b;
cnt[i] = cnt[hull[t]] + 1;
}
}
t = min((int) hull.size() - 1, t);
t = max(0, t);
llint single =
(llint)(I[i].second - I[0].first + 1) * (I[i].second - I[0].first + 1) +
cost;
if (single <= f[i]) {
f[i] = single;
cnt[i] = 1;
}
A[i] = -2LL * (I[i + 1].first - 1);
B[i] = f[i] + (llint)(I[i + 1].first - 1) * (I[i + 1].first - 1) -
(llint)max(0, I[i].second - I[i + 1].first + 1) *
max(0, I[i].second - I[i + 1].first + 1);
insert(i, &t);
}
return {f[n - 1], cnt[n - 1]};
}
llint take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
n = nn; m = mm; k = kk;
for (int i = 0; i < n; ++i) P.emplace_back(r[i], c[i]);
I = get_intervals(n, r, c);
n = (int)I.size();
I.emplace_back(1e9, 1e9);
k = min(k, n);
llint lo = 0, hi = (llint) 2 * m * m;
while (lo < hi) {
llint mid = (lo + hi) / 2;
auto val = dp(mid);
if (val.second > k) lo = mid + 1; else hi = mid;
}
auto sol = dp(lo);
dp(lo - 1);
return sol.first - (llint) k * lo;
}
