#include <bits/stdc++.h>
typedef long double ld;
typedef long long ll;
using namespace std;
const ld eps = 1e-9;
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pair<int, int>> pts_uf, pts; // unfiltered, filtered
for(int i = 0; i < n; i++) {
if(r[i] > c[i]) swap(r[i], c[i]);
pts_uf.push_back({r[i], c[i]});
}
sort(pts_uf.begin(), pts_uf.end());
for(int i = 0; i < n; i++) {
while(!pts.empty() && (pts.back().first == pts_uf[i].first)) {
pts.pop_back();
}
if(pts.empty() || pts.back().second < pts_uf[i].second) {
pts.push_back(pts_uf[i]);
}
}
n = pts.size();
auto isect = [](pair<ld, pair<ld, int>> l1, pair<ld, pair<ld, int>> l2) {
return (l2.second.first - l1.second.first) / (l2.first - l1.first);
};
auto try_penalty = [&](ld penalty) { // CHT
vector<pair<ld, int>> dp(n + 1);
deque<pair<ld, pair<ld, int>>> hull;
dp[0] = {0, 0};
hull.push_back({0, {0, 0}});
for(int i = 1; i <= n; i++) {
while(hull.size() > 1 && isect(hull[0], hull[1]) < pts[i - 1].first) {
hull.pop_front();
}
dp[i] = {hull[0].first * pts[i - 1].second + hull[0].second.first, hull[0].second.second};
dp[i].first += (ld) pts[i - 1].second * pts[i - 1].second;
dp[i].first -= penalty, dp[i].second++;
if(i < n) { // insert line
pair<ld, pair<ld, int>> to_add = {-2 * pts[i - 1].second, dp[i]};
ld df = max(0, pts[i - 1].second - pts[i].first);
to_add.second.first += (ld) pts[i].first * pts[i].first - df * df;
while(hull.size() > 1 && isect(hull[hull.size() - 2], hull[hull.size() - 1]) > isect(hull[hull.size() - 2], to_add)) {
hull.pop_back();
}
hull.push_back(to_add);
}
}
return dp[n];
};
ld lb = 0, ub = 1e12;
for(int it = 0; it < 400; it++) {
ld mid = (lb + ub) / 2;
pair<ld, int> res = try_penalty(mid);
if(res.second <= k) {
ub = mid;
} else {
lb = mid;
}
}
pair<ld, int> res = try_penalty(ub);
return (ll) (res.first + (res.second + eps) * ub);
}
