#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 <= r0);
assert(l1 <= r1);
if (r0 < l1) return 0;
if (r1 < l0) return 0;
if (l0 <= l1 && r0 >= r1) return (r1-l1+1) * (r1-l1+1);
if (l1 <= l0 && r1 >= r0) return (r0-l0+1) * (r0-l0+1);
if (l1 >= r0) return (l1-r0+1) * (l1-r0+1);
if (l0 >= r1) return (l0-r1+1) * (l0-r1+1);
assert(0);
}
pair<ll, int> go(ld 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]; });
ld lo = 0, hi = 1e18;
while (hi-lo > 1e-6) {
ld ce = (hi+lo)/2;
auto [cost, cnt] = go(ce);
if (cnt > k) lo = ce;
else hi = ce;
}
auto [cost, cnt] = go(hi);
return cost;
}
