#include <bits/stdc++.h>
#include "aliens.h"
using ll = long long;
using std::vector;
using std::pair;
ll floor_div(const ll a, const ll b) {
const ll q = a / b;
const ll r = a - b * q;
return r >= 0 ? q : q - 1;
}
struct Line {
ll a, b;
ll eval(const ll x) const {
return a * x + b;
}
};
struct CHT {
std::deque<Line> line;
ll change(const Line s, const Line t) const {
return floor_div(t.b - s.b, s.a - t.a);
}
void add(const Line l) {
int size = line.size();
while (size >= 2) {
const Line m = line[size - 1], n = line[size - 2];
if (change(n, m) >= change(m, l)) {
line.pop_back();
size -= 1;
} else {
break;
}
}
line.push_back(l);
}
ll get(const ll x) {
while (line.size() >= 2 and line[0].eval(x) > line[1].eval(x)) {
line.pop_front();
}
return line[0].eval(x);
}
};
constexpr ll inf = 1000000000000;
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> lr(n);
for (int i = 0; i < n; ++i) {
lr[i] = std::minmax(r[i], c[i]);
lr[i].second += 1;
}
std::sort(lr.begin(), lr.end());
vector<pair<int, int>> need;
for (const auto& [l, r] : lr) {
if (need.empty()) {
need.emplace_back(l, r);
} else {
auto& [a, b] = need.back();
if (a == l) {
b = r;
} else if (b < r) {
need.emplace_back(l, r);
}
}
}
n = need.size();
k = std::min(k, n);
const auto solve = [&](const ll lambda) {
ll last = 0;
CHT cht;
for (int i = 0; i < n; ++i) {
const auto& [l, r] = need[i];
const ll dif = i == 0 ? 0 : need[i - 1].second - l;
cht.add({-2 * l, (ll)l * l + last - (dif > 0 ? dif * dif : 0)});
last = cht.get(r) + (ll)r * r + lambda;
}
return last - lambda * k;
};
ll min = -1, max = inf + 1;
while (max - min > 2) {
const ll m1 = min + (max - min) / 2;
const ll m2 = m1 + 1;
if (solve(m1) >= solve(m2)) {
max = m2;
} else {
min = m1;
}
}
return solve(min + 1);
}
