#include <bits/stdc++.h>
#include "aliens.h"
#define ar array
using namespace std;
using ll = long long;
using lll = __int128;
//using ld = long double;
int n, m, k;
vector<ar<ll, 2>> p;
vector<ll> l, r;
vector<int> s;
const ll INF = 1LL<<60;
ll overlap(ll l0, ll r0, ll l1, ll r1) {
assert(l0 <= l1);
assert(l0 <= r0);
assert(l1 <= r1);
// completely inside
if (r1 <= r0) return (r1-l1+1)*(r1-l1+1);
// completely outside
if (r0 < l1) return 0;
return (r0-l1+1)*(r0-l1+1);
}
pair<ll, int> go(ll penalty) {
ll real_cost = 0;
int used = 0;
ll cl = -INF;
ll cr = -INF;
//ld tiebreak = 0;
//ld tiebreak_inc = 1.0l/n;
for (int i : s) {
lll was_w = cr-cl+1;
lll extend_w = max(cr, r[i]) - min(cl, l[i]) + 1;
lll extend_cost = extend_w*extend_w - was_w*was_w;
lll new_w = r[i]-l[i]+1;
lll new_cost = new_w*new_w - overlap(cl, cr, l[i], r[i]);
if (extend_cost < new_cost + penalty /* + tiebreak*/) {
real_cost += extend_cost;
cl = min(cl, l[i]);
cr = max(cr, r[i]);
} else {
//if (cl > -INF) cerr << cl << ':' << cr << ' ';
real_cost += new_cost;
cl = l[i];
cr = r[i];
++used;
}
//tiebreak += tiebreak_inc;
}
//if (cl > -INF) cerr << cl << ':' << cr << '\n';
return {real_cost, used};
}
ll take_photos(int n_, int m_, int k_, vector<int> r_, vector<int> c_) {
n = n_, m = m_, k = k_;
l.resize(n);
r.resize(n);
s.resize(n);
for (int i = 0; i < n; ++i) {
l[i] = min(r_[i], c_[i]);
r[i] = max(r_[i], c_[i]);
}
iota(s.begin(), s.end(), 0);
sort(s.begin(), s.end(), [&](int i, int j) { return l[i] < l[j]; });
ll lo = 0, hi = INF;
while (lo != hi) {
ll ce = lo + (hi-lo)/2;
auto [cost, cnt] = go(ce);
if (cnt > k) lo = ce+1;
else hi = ce;
}
auto [cost, cnt] = go(lo);
return cost;
}
