#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
struct line {
long long a, b;
int c;
long long div(long long a, long long b) const {
return a / b - ((a ^ b) < 0 && a % b);
}
long long slope(const line &o) const {
return div(o.b - b, a - o.a);
}
long long eval(long long x) const {
return a * x + b;
}
};
deque<line> hull;
void add(line l) {
while (hull.size() > 1 && hull.end()[-2].slope(hull.back()) >= hull.back().slope(l)) {
hull.pop_back();
}
hull.push_back(l);
}
pair<long long, int> qry(long long x) {
while (hull.size() > 1 && hull[0].eval(x) > hull[1].eval(x)) {
hull.pop_front();
}
return {hull[0].eval(x), hull[0].c};
}
vector<array<int, 2>> cands;
pair<long long, int> count(long long pen) {
deque<line>().swap(hull);
long long dp = 0;
int lst = 0, cnt = 0;
for (auto [x, y] : cands) {
int l = max(0, lst - x);
add({-2 * x, dp + (long long) x * x - (long long) l * l, cnt});
tie(dp, cnt) = qry(y);
dp += (long long) y * y + pen;
++cnt;
lst = y;
}
return {dp, cnt};
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<int> mi(m, m + 1);
for (int i = 0; i < n; ++i) {
if (r[i] > c[i]) {
swap(r[i], c[i]);
}
mi[c[i]] = min(mi[c[i]], r[i]);
}
for (int i = 0; i < m; ++i) {
if (mi[i] != m + 1) {
while (cands.size() && cands.back()[0] >= mi[i]) {
cands.pop_back();
}
cands.push_back({mi[i], i + 1});
}
}
long long L = 0, R = (long long) m * m, res = -1;
while (L <= R) {
auto md = (L + R) / 2;
if (count(md).second <= k) {
res = md;
R = md - 1;
} else {
L = md + 1;
}
}
return count(res).first - k * res;
}
