#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
auto operator<<(auto&o, auto p)->decltype(p.first, o){return o << '(' << p.first << ", " << p.second << ')';}
auto operator<<(auto&o, auto x)->decltype(x.end(), o){o << '{';int i=2; for (auto e : x)o << (", ")+i << e, i=0; return o << '}';}
#define LOG(X...)cerr<<"["#X"]: ",[](auto...$){((cerr<<$<<"; "),...)<<endl;}(X);
#else
#define LOG(X...)(void)0
#endif
void mn(int &a, int b) {
a = min(a, b);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<int> row(m, INT_MAX), column(m, INT_MAX);
for (int i = 0; i < n; i++) {
mn(row[r[i]], c[i]);
mn(column[c[i]], r[i]);
}
auto check = [&](long long lambda) -> pair<long long, int> {
long long value = 0;
stack<pair<int, int>> recs;
for (int rc = 0; rc < m; rc++) {
int mrc = min(column[rc], row[rc]);
if (mrc > rc)
continue;
auto added = [&](pair<int, int> t, pair<int, int> a) -> long long {
int size = t.second - t.first + 1;
if (t.first > a.second)
return (long long)size * size;
int sizeDif = a.second - t.first + 1;
return (long long)size * size - (long long)sizeDif * sizeDif;
};
while (!recs.empty() && recs.top().first >= mrc) {
auto t = recs.top();
recs.pop();
value -= lambda;
pair<int, int> last = {-1, -1};
if (!recs.empty())
last = recs.top();
value -= added(t, last);
}
if (recs.empty()) {
value += added({mrc, rc}, {-1, -1}) + lambda;
recs.push({mrc, rc});
continue;
}
auto t = recs.top();
recs.pop();
pair<int, int> last = {-1, -1};
if (!recs.empty())
last = recs.top();
long long va = added({t.first, rc}, last) - added(t, last);
long long vna = added({mrc, rc}, t) + lambda;
if (vna < va) {
value += vna;
recs.push(t);
recs.push({mrc, rc});
} else {
value += va;
recs.push({t.first, rc});
}
}
int size = recs.size();
while (!recs.empty()) {
recs.pop();
}
return {value, size};
};
long long left = 0;
long long right = 1e12;
while (left < right) {
long long mid = (left + right) / 2;
auto ch = check(mid);
if (ch.second > k)
left = mid + 1;
else
right = mid;
}
auto ch = check(left);
return ch.first - left * k;
}
