#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll = long long;
using ld = long double;
using pr = pair<int, int>;
const int MOD = 1e9+7, MAXA = 1e6;
ll olap(int x, int d, int nx, int nd) {
ll olap = max(x + d - nx, -1); // overlap
return (olap+1) * (olap+1);
}
ll connect(int x, int d, int nx, int nd) {
ll newx = nx+nd - x;
return (newx+1) * (newx+1) - ((d+1) * (d+1) + (nd+1) * (nd+1) - olap(x, d, nx, nd));
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
set<pr> block; // diagonal, distance from diagonal
vector<pr> pos(n);
for (int i = 0; i < n; i++) {
if (r[i] > c[i]) swap(r[i], c[i]);
pos[i] = {r[i], c[i]};
}
sort(pos.begin(), pos.end());
{
auto [x, y] = pos[0];
// if (x > y) swap(x, y);
block.insert({x, abs(x - y)});
}
for (int i = 1; i < n; i++) {
auto [x, y] = pos[i];
if (x > y) swap(x, y);
int d = abs(x - y);
auto [px, pd] = *--block.end();
if (px <= x && pd + px >= x && px >= y && px + pd <= y) continue;
else {
block.insert({x, d});
}
}
set<array<ll, 5>> pq;
int total = 0;
{
int temp = block.begin()->second;
total = (temp+1) * (temp+1);
}
for (auto [x, d] : block) {
auto it = next(block.find({x, d}));
if (it == block.end()) continue;
auto [nx, nd] = *it;
total = total - olap(x, d, nx, nd) + (nd+1) * (nd+1);
pq.insert({connect(x, d, nx, nd), x, d, nx, nd});
}
while (pq.size()+1 > k) {
auto [con, x, d, nx, nd] = *pq.begin();
pq.erase(pq.begin());
total += con;
int newx = x;
int newd = nx+nd - x;
if (block.find({x, d}) != block.begin()) {
auto pre = prev(block.find({x, d}));
auto [px, pd] = *pre;
pq.erase({connect(px, pd, x, d), px, pd, x, d});
pq.insert({connect(px, pd, newx, newd), px, pd, newx, newd});
}
if (block.find({nx, nd}) != --block.end()) {
auto nex = next(block.find({nx, nd}));
auto [nexx, nexd] = *nex;
pq.erase({connect(nx, nd, nexx, nexd), nx, nd, nexx, nexd});
pq.insert({connect(newx, newd, nexx, nexd), newx, newd, nexx, nexd});
}
block.erase({x, d});
block.erase({nx, nd});
block.insert({newx, newd});
}
return total;
}
