#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using vb = vector<bool>;
using ll = __int128;
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
ll sq(ll x) { return x * x; }
struct Line {
ll m, b, k;
ll operator()(ll x) {
return m * x + b;
}
};
const ll INF = 5e18;
long long take_photos(int n, int m, int k, vi r, vi c) {
vector<ii> points(n);
forn(i, n) points[i] = minmax(r[i], c[i]);
sort(all(points), [&](const ii &lhs, const ii &rhs) {
if (lhs.fst != rhs.fst) return lhs.fst < rhs.fst;
return lhs.snd > rhs.snd;
});
vector<ii> nonDominated = {points[0]};
forsn(i, 1, n) {
if (nonDominated.back().snd < points[i].snd) {
nonDominated.pb(points[i]);
}
}
points = nonDominated;
n = sz(points);
k = min(k, n);
auto check = [&](ll lmd) {
vector<pair<ll, ll>> dp(n + 1, {INF, 0});
dp[0] = {0, 0};
deque<Line> hull;
forn(i, n) {
Line l = {-2LL * (points[i].fst - 1LL),
lmd + dp[i].fst + sq(points[i].fst - 1LL) - (i == 0 ? 0 : sq(max(points[i - 1].snd - points[i].fst + 1LL, 0LL))),
dp[i].snd + 1};
while (sz(hull) >= 2 && (end(hull)[-1].b - end(hull)[-2].b) * (end(hull)[-2].m - l.m) >= (l.b - end(hull)[-2].b) * (end(hull)[-2].m - end(hull)[-1].m)) hull.pop_back();
hull.pb(l);
while (sz(hull) >= 2 && hull[0](points[i].snd) >= hull[1](points[i].snd)) hull.pop_front();
Line best = hull.front();
dp[i + 1] = {best(points[i].snd) + sq(points[i].snd), best.k};
}
return dp[n];
};
ll lo = -1e15 - 500, hi = 1e15 + 500;
while (hi - lo > 1) {
ll mid = (lo + hi) / 2;
if (check(mid).snd >= k) lo = mid;
else hi = mid;
}
ll cost_lo = check(lo).fst - k * lo;
ll cost_hi = check(hi).fst - k * hi;
return max(cost_lo, cost_hi);
}
