#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;
for (int i = 0; i < n; i++)
all.emplace_back(min(r[i], c[i]), max(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 = 1LL * m * m;
n = (int)segs.size();
while (binl < binr) {
ll mid = (binl + binr) / 2;
vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
ct[0] = 0;
deque<array<ll, 3>> lin;
lin.push_back({ -2 * (ll)segs[0].first,
dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first,
0LL });
auto qry = [&](const array<ll, 3>& L, ll x) { return L[0] * x + L[1]; };
for (int i = 1; i <= n; i++) {
while (lin.size() > 1) {
ll a = qry(lin[0], segs[i - 1].second);
ll 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;
} else {
break;
}
}
auto [mm, bb, in] = lin.front();
dp[i] = (ll)segs[i - 1].second * mm + bb
+ sq(segs[i - 1].second) + 2LL * (ll)segs[i - 1].second + 1
+ mid;
ct[i] = ct[in] + 1;
if (i < n) {
lin.push_back({ -2 * (ll)segs[i].first,
dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first),
(ll)i });
}
}
if (ct[n] > k) binl = mid + 1;
else binr = mid;
}
vector<ll> dp(n + 1), ct(n + 1, (ll)INT_MAX);
ct[0] = 0;
deque<array<ll, 3>> lin;
lin.push_back({ -2 * (ll)segs[0].first,
dp[0] + sq(segs[0].first) - 2LL * (ll)segs[0].first,
0LL });
auto qry = [&](const array<ll, 3>& L, ll x) { return L[0] * x + L[1]; };
for (int i = 1; i <= n; i++) {
while (lin.size() > 1) {
ll a = qry(lin[0], segs[i - 1].second);
ll 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;
} else {
break;
}
}
auto [mm, bb, in] = lin.front();
dp[i] = (ll)segs[i - 1].second * mm + bb
+ sq(segs[i - 1].second) + 2LL * (ll)segs[i - 1].second + 1
+ binl;
ct[i] = ct[in] + 1;
if (i < n) {
lin.push_back({ -2 * (ll)segs[i].first,
dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first),
(ll)i });
}
}
return dp.back() - 1LL * k * binl;
}
