#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
ll sq(ll a) {
return a * a;
}
constexpr ll inf = 3e18;
struct Line {
ll k = 0, b = inf;
int idx = -1;
double last = -inf;
ll eval(ll x) {
return k * x + b;
}
double intersect(Line a) {
return (a.b - b) / double(k - a.k);
}
};
struct CHT {
deque<Line> t;
void add(Line a) {
while (t.size() > 1 && a.intersect(t.end()[-2]) < t.back().last) {
t.pop_back();
}
if (!t.empty()) {
a.last = a.intersect(t.back());
}
t.push_back(a);
}
Line query(ll x) {
while (t.size() > 1 && t[1].eval(x) < t[0].eval(x)) {
t.pop_front();
}
return t[0];
}
};
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for (int i = 0; i < n; ++i) {
if (r[i] < c[i]) {
swap(r[i], c[i]);
}
++r[i];
}
vector<int> ord(n);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return r[i] != r[j] ? r[i] < r[j] : c[i] > c[j];
});
vector<int> stk;
for (int i: ord) {
while (!stk.empty() && c[stk.back()] >= c[i]) {
stk.pop_back();
}
stk.push_back(i);
}
vector<int> nr = {-1}, nc = {-1};
for (int i: stk) {
nr.push_back(r[i]), nc.push_back(c[i]);
}
swap(r, nr), swap(c, nc);
n = r.size();
k = min(k, n - 1);
ll L = 0, R = ll(m) * m + 1;
ll ans = 0;
while (L + 1 < R) {
ll mid = (L + R) / 2;
CHT t;
vector<ll> dp(n, inf);
dp[0] = 0;
vector<int> cnt(n);
for (int i = 0; i < n; ++i) {
if (i > 0) {
Line line = t.query(r[i]);
dp[i] = line.eval(r[i]) + mid + sq(r[i]);
cnt[i] = cnt[line.idx] + 1;
}
if (i != n - 1) {
t.add({-2 * c[i + 1], dp[i] - sq(max(0, r[i] - c[i + 1])) + sq(c[i + 1]), i});
}
}
if (cnt[n - 1] <= k) {
ans = dp[n - 1];
R = mid;
} else {
L = mid;
}
}
return ans - k * R;
}
