#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Line {
ll m, b;
int cnt;
pair<ll, int> get(ll x) const { return {m * x + b, cnt}; }
};
struct CHT {
deque<Line> dq;
bool bad(const Line &a, const Line &b, const Line &c) {
return (b.b - a.b) * (b.m - c.m) >= (c.b - b.b) * (a.m - b.m);
}
void add(ll m, ll b, int cnt) {
Line cur{m, b, cnt};
while (dq.size() && dq.back().m == cur.m) {
if (dq.back().b <= cur.b)
return;
dq.pop_back();
}
while (dq.size() >= 2 && bad(dq[dq.size() - 2], dq.back(), cur)) {
dq.pop_back();
}
dq.push_back(cur);
}
pair<ll, int> qry(ll x) {
while (dq.size() >= 2 && dq[1].get(x) < dq[0].get(x)) {
dq.pop_front();
}
return dq[0].get(x);
}
};
vector<pair<int, int>> pt;
pair<int, ll> calc(ll penal) {
CHT cht;
pair<ll, int> dp = {0, 0};
for (int i = 0; i < pt.size(); ++i) {
auto &[L, R] = pt[i];
ll over = 0;
if (i) {
over = max(over, 1ll * pt[i - 1].second - L + 1);
}
cht.add(-2 * L, dp.first - over * over + L * L, dp.second);
ll x = R + 1;
dp = cht.qry(x);
dp.first += x * x + penal;
dp.second++;
}
return dp;
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
{
vector<pair<int, int>> tmp(n);
for (int i = 0; i < n; ++i) {
tmp[i] = minmax(r[i], c[i]);
}
ranges::sort(tmp);
for (auto &[L, R] : tmp) {
while (pt.size() && R <= pt.back().second) {
continue;
}
pt.push_back({L, R});
}
}
ll lo = 0, hi = 1ll * m * m, ans;
while (hi - lo + 1) {
ll mid = (lo + hi) / 2;
auto dp = calc(mid);
if (dp.second <= k) {
hi = mid - 1;
ans = dp.first;
} else
lo = mid + 1;
}
return ans - lo * k;
}
