#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; };
auto kill = [&](array<ll, 3> a, array<ll, 3> b, array<ll, 3> c) {
return (a[1] - c[1]) * (b[0] - a[0]) <= (a[1] - b[1]) * (c[0] - a[0]);
};
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) {
array<ll, 3> tmp = {
-2 * (ll)segs[i].first,
dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) -
sq(max(0, segs[i - 1].second - segs[i].first + 1)),
(ll)i};
while (lin.size() >= 2 && kill(lin[lin.size() - 2], lin.back(), tmp)) {
lin.pop_back();
}
lin.push_back(tmp);
}
}
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) {
array<ll, 3> tmp = {
-2 * (ll)segs[i].first,
dp[i] - 2LL * (ll)segs[i].first + sq(segs[i].first) -
sq(max(0, segs[i - 1].second - segs[i].first + 1)),
(ll)i};
while (lin.size() >= 2 && kill(lin[lin.size() - 2], lin.back(), tmp)) {
lin.pop_back();
}
lin.push_back(tmp);
}
}
return dp.back() - 1LL * k * binl;
}
