#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> all(n);
for (int i = 0; i < n; i++)
all.emplace_back(minmax(r[i], c[i]));
sort(all.begin(), all.end(), [&](pair<int, int> a, pair<int, int> b) {
if (a.first != b.first)
return a.first < b.first;
return a.second > b.second;
});
vector<pair<int, int>> segs;
for (auto [l, r] : all)
if (segs.empty()) {
segs.emplace_back(l, r);
} else {
auto [l2, r2] = segs.back();
if (r2 < r) {
segs.emplace_back(l, r);
}
}
auto sq = [&](ll x) { return x * x; };
ll binl = 0, binr = m * m;
n = segs.size();
while (binl < binr) {
ll mid = (binl + binr) / 2;
vector<ll> dp(n + 1), ct(n + 1, INT_MAX);
ct[0] = 0;
deque<array<ll, 3>> lin;
lin.push_back({-2 * (segs[0].first),
dp[0] + sq(segs[0].first) - 2 * (segs[0].first),
0ll}); // slope, offset, in
auto qry = [&](array<ll, 3> all, ll x) { return all[0] * x + all[1]; };
for (int i = 1; i <= n; i++) {
while (lin.size() > 1) {
ll a = qry(lin[0], segs[i - 1].second),
b = qry(lin[1], segs[i - 1].second);
if (a > b) {
lin.pop_front();
} else if (a == b) {
if (ct[lin[0][2]] >= ct[lin[1][2]])
lin.pop_front();
} else {
break;
}
}
auto [m, b, in] = lin.front();
dp[i] = segs[i - 1].second * m + b + sq(segs[i - 1].second) +
2 * segs[i - 1].second + 1 + mid;
ct[i] = ct[in] + 1;
if (i < n)
lin.push_back(
{dp[in] - 2 * segs[i].first + sq(segs[i].first), segs[i].first});
}
if (ct[n] > k) {
binr = mid - 1;
} else {
binl = mid;
}
}
vector<ll> dp(n + 1), ct(n + 1, INT_MAX);
ct[0] = 0;
deque<array<ll, 3>> lin;
lin.push_back({-2 * (segs[0].first),
dp[0] + sq(segs[0].first) - 2 * (segs[0].first),
0ll}); // slope, offset, in
auto qry = [&](array<ll, 3> all, ll x) { return all[0] * x + all[1]; };
for (int i = 1; i <= n; i++) {
while (lin.size() > 1) {
ll a = qry(lin[0], segs[i - 1].second),
b = qry(lin[1], segs[i - 1].second);
if (a > b) {
lin.pop_front();
} else if (a == b) {
if (ct[lin[0][2]] >= ct[lin[1][2]])
lin.pop_front();
} else {
break;
}
}
auto [m, b, in] = lin.front();
dp[i] = segs[i - 1].second * m + b + sq(segs[i - 1].second) +
2 * segs[i - 1].second + 1 + binl;
ct[i] = ct[in] + 1;
if (i < n)
lin.push_back(
{dp[in] - 2 * segs[i].first + sq(segs[i].first), segs[i].first});
}
return dp.back() - k * binl;
}
