#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const ll inf = 1e18;
struct DS{
struct line{
ld k, b;
int i;
line(ld ks, ld bs, int is){
k = ks; b = bs; i = is;
}
ld operator ()(int x){
return k * x + b;
}
ld inter(line f){
return (f.b - b) / (k - f.k);
}
};
deque<line> q;
void add(ld k, ld b, int i){
line f(k, b, i);
while (q.size() >= 2 && q[q.size() - 2].inter(f) <= q[q.size() - 2].inter(q.back())){
q.pop_back();
}
q.pb(f);
}
pair<ld, int> get(int x){
while (q.size() >= 2 && q[0].inter(q[1]) <= x){
q.pop_front();
}
return {q[0](x), q[0].i};
}
void clear(){
q.clear();
}
};
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pii> all;
for (int i = 0; i < n; i++){
if (r[i] > c[i]) swap(r[i], c[i]);
all.pb({r[i], c[i]});
}
auto cmp = [&](pii x, pii y){
if (x.ff != y.ff) return x.ff < y.ff;
return x.ss > y.ss;
};
sort(all.begin(), all.end(), cmp);
auto sq = [&](ll x){
return x * x;
};
vector<pii> f = {{-1, -1}};
int X = -1, Y = -1;
for (auto [x, y]: all){
if (X < x && Y < y){
f.pb({x, y});
X = x; Y = y;
}
}
n = (int) f.size() - 1; k = min(k, n);
vector<pair<ld, int>> dp(n + 1);
DS T;
auto F = [&](ld M){
T.clear();
for (int i = 1; i <= n; i++){
ll h = f[i - 1].ss - f[i].ff + 1;
if (h > 0) h = sq(h);
else h = 0;
T.add(-2 * (f[i].ff - 1), dp[i - 1].ff + sq(f[i].ff - 1) - h, i);
auto [v, j] = T.get(f[i].ss);
dp[i] = {sq(f[i].ss) + v + M, dp[j - 1].ss + 1};
}
return dp[n];
};
ld L = 0, R = 1e12;
while ((R - L) >= 1e-6){
ld M = (L + R) / 2;
if (F(M).ss < k){
R = M;
}
else {
L = M;
}
}
auto [v, x] = F(L);
return (ll) round(v - k * L);
}
