#include "aliens.h"
#include <bits/stdc++.h>
#ifdef __LOCAL__
#include <debug_local.h>
#endif
using namespace std;
using ll = long long;
struct Line {
ll m = 0, c = 0;
int cnt = 0;
Line(ll _m, ll _c, int _cnt) : m(_m), c(_c), cnt(_cnt) { }
ll get(ll x) { return m * x + c; }
double intersection(Line o) { return (double) (o.c - c) / (double) (m - o.m); }
bool good(Line l2, Line l3) { return __int128(l2.c - c) * (l2.m - l3.m) < __int128(l3.c - l2.c) * (m - l2.m); }
};
struct CHT {
deque<Line> hull;
void insert(Line l) {
while (hull.size() > 1) {
auto last = hull.end()[-1];
auto p_last = hull.end()[-2];
if (p_last.good(last, l)) break;
hull.pop_back();
}
hull.push_back(l);
}
pair<ll, int> query(ll x) {
while (hull.size() > 1 && hull[0].get(x) > hull[1].get(x)) {
hull.pop_front();
}
return {hull[0].get(x), hull[0].cnt};
}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> a;
for (int i = 0; i < n; i++) {
r[i]++, c[i]++;
a.push_back({min(r[i], c[i]) - 1, max(r[i], c[i])});
}
sort(a.begin(), a.end(), [&](auto i, auto j) {
if (i.first != j.first) return i.first < j.first;
return i.second > j.second;
});
{
vector<pair<int, int>> final;
auto last = make_pair(-1, -1);
for (int i = 0; i < n; i++) {
auto [x, y] = a[i];
if (x >= last.first && y <= last.second) continue;
final.push_back(a[i]);
last = a[i];
}
a = final;
}
auto sq = [&](ll x) {
return 1LL * x * x;
};
a.insert(a.begin(), {0, 0});
n = a.size() - 1;
auto check = [&](ll m) {
CHT cht;
cht.insert(Line(-a[1].first, sq(a[1].first), 0));
for (int i = 1; i <= n; i++) {
auto x = cht.query(2 * a[i].second);
ll dp = x.first + sq(a[i].second) + m;
if (i == n) return pair<ll, int> {dp, x.second + 1};
cht.insert(Line(-a[i + 1].first, dp - sq(max(0, a[i].second - a[i + 1].first)) + sq(a[i + 1].first), x.second + 1));
}
return pair<ll, int> {0, 0};
};
ll lo = 0, hi = 1e13;
while (lo < hi) {
ll mid = (lo + hi) >> 1;
if (check(mid).second <= k) hi = mid;
else lo = mid + 1;
}
auto x = check(lo);
return x.first - 1LL * k * lo;
}
