#include <bits/stdc++.h>
using namespace std;
const int N = 1000000;
struct line {
long long m, b, p;
};
long long offset[N], edge[N];
long long floor_div(long long a, long long b) {
return a / b - ((a ^ b) < 0 && a % b != 0);
}
long long intersect(line a, line b) {
return floor_div(a.b - b.b, b.m - a.m);
}
long long evaluate(line a, long long x) {
return a.m * x + a.b;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
fill(edge, edge + m, -1);
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
edge[r[i]] = max(edge[r[i]], (long long) c[i]);
}
offset[0] = 1;
for (int i = 1; i < m; ++i) {
edge[i] = max(edge[i], edge[i - 1]);
offset[i] = offset[i - 1] - 2 * i + 1;
}
long long ans = (long long) m * m;
long long low = 0, high = ans;
while (low < high) {
long long mid = (low + high) / 2;
long long cost = 0, photos = 0;
deque<line> hull;
int i = m - 1;
for ( ; i >= 0 && edge[i] != -1; --i) {
if (i == m - 1 || edge[i] != edge[i + 1]) {
if (!hull.empty()) {
cost = evaluate(hull[0], i) - offset[i];
photos = hull[0].p;
}
int j = min(i, (int) edge[i]);
line add = {-2 * edge[i], 2 * edge[i] * j + cost + mid + offset[j], photos + 1};
while (hull.size() >= 2 && intersect(add, hull.back()) >= intersect(hull.back(), hull[hull.size() - 2])) {
hull.pop_back();
}
hull.push_back(add);
}
if (!hull.empty()) {
while (hull.size() >= 2 && evaluate(hull[0], i - 1) > evaluate(hull[1], i - 1)) {
hull.pop_front();
}
}
}
cost = evaluate(hull[0], i) - (i == -1 ? 0 : offset[i]);
photos = hull[0].p;
if (photos <= k) {
ans = cost - k * mid;
high = mid;
} else {
low = mid + 1;
}
}
return ans;
}
