#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
struct Point {
ll r, c;
};
struct Line {
ll m, b;
int cnt;
ll eval(ll x) { return m * x + b; }
};
struct ConvexHull {
vector<Line> lines;
int ptr = 0;
void add(ll m, ll b, int cnt) {
Line l = {m, b, cnt};
while (lines.size() >= 2) {
Line l1 = lines[lines.size() - 2];
Line l2 = lines.back();
// Kesishish nuqtalarini tekshirish (Aliens Trick + CHT mantiqi)
if ((__int128)(l2.b - l1.b) * (l2.m - l.m) >= (__int128)(l.b - l2.b) * (l1.m - l2.m))
lines.pop_back();
else break;
}
lines.push_back(l);
}
pair<ll, int> query(ll x) {
if (ptr >= lines.size()) ptr = lines.size() - 1;
while (ptr + 1 < lines.size() && lines[ptr].eval(x) > lines[ptr + 1].eval(x))
ptr++;
return {lines[ptr].eval(x), lines[ptr].cnt};
}
void clear() { lines.clear(); ptr = 0; }
};
pair<ll, int> solve(ll lambda, int n, const vector<Point>& p) {
vector<ll> dp(n + 1);
vector<int> cnt(n + 1);
ConvexHull cht;
cht.add(-2 * p[0].r, p[0].r * p[0].r - 2 * p[0].r + 1, 0);
for (int i = 1; i <= n; i++) {
auto res = cht.query(p[i - 1].c);
dp[i] = res.first + p[i - 1].c * p[i - 1].c + 2 * p[i - 1].c + lambda;
cnt[i] = res.second + 1;
if (i < n) {
ll overlap = max(0LL, p[i - 1].c - p[i].r + 1);
ll b = dp[i] + p[i].r * p[i].r - 2 * p[i].r + 1 - overlap * overlap;
cht.add(-2 * p[i].r, b, cnt[i]);
}
}
return {dp[n], cnt[n]};
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<Point> raw(n);
for (int i = 0; i < n; i++) {
raw[i] = {min(r[i], c[i]), max(r[i], c[i])};
}
sort(raw.begin(), raw.end(), [](Point a, Point b) {
if (a.r != b.r) return a.r < b.r;
return a.c > b.c;
});
vector<Point> p;
for (auto& pt : raw) {
if (p.empty() || pt.c > p.back().c) p.push_back(pt);
}
n = p.size();
k = min(k, n);
ll low = 0, high = (ll)m * m, ans_lambda = high;
while (low <= high) {
ll mid = low + (high - low) / 2;
if (solve(mid, n, p).second <= k) {
ans_lambda = mid;
high = mid - 1;
} else {
low = mid + 1;
}
}
auto final_res = solve(ans_lambda, n, p);
return final_res.first - (ll)k * ans_lambda;
}
