#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
typedef pair<long long, long long> pll;
typedef pair<int, pll> pill;
const int N = 100005;
void modify(vector<pll> &a) {
vector<pll> b = a; a.clear();
sort(b.begin(), b.end(), [&] (pll x, pll y) {
return (x.first == y.first) ? x.second > y.second : x.first < y.first;
});
int mx = 0;
for (auto i : b) {
if (mx >= i.second) continue;
mx = i.second, a.push_back(i);
}
}
int trace[N];
long long f[N];
long long val[N];
vector<pll> a;
deque<pill> dq;
long long cal(pll x, pll y) {
return x.first * y.first + x.second + y.second;
}
bool bad(pll x, pll y, pll z) {
return (x.second - z.second) * (z.first - y.first) >= (y.second - z.second) * (z.first - x.first);
}
void add(pll x, int id) {
while (dq.size() >= 2 && bad(dq[dq.size() - 2].second, dq[dq.size() - 1].second, x)) dq.pop_back();
dq.push_back(pill(id, x));
}
void query(pll x, int id) {
while (dq.size() >= 2 && cal(x, dq[0].second) > cal(x, dq[1].second)) dq.pop_front();
trace[id] = dq[0].first, f[id] = cal(x, dq[0].second);
}
int solve(long long x) {
int n = a.size();
for (int i = 1; i < n; ++i) {
val[i] = max(0LL, a[i - 1].second - a[i].first), val[i] *= val[i];
}
dq.clear();
for (int i = 1; i <= n; ++i) {
add(pll(-2 * a[i - 1].first, a[i - 1].first * a[i - 1].first - val[i - 1] + f[i - 1]), i - 1);
query(pll(a[i - 1].second, a[i - 1].second * a[i - 1].second + x), i);
}
int cnt = 0, cur = n;
while (cur) cnt++, cur = trace[cur];
return cnt;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (int i = 0; i < n; ++i) {
a.push_back(pll(min(r[i], c[i]), max(r[i], c[i]) + 1));
}
modify(a), n = a.size();
long long lo = 0, hi = 1e12;
while (lo < hi) {
long long mid = (lo + hi) >> 1;
if (solve(mid) <= k) hi = mid; else lo = mid + 1;
}
solve(lo); return f[n] - lo * k;
}
