#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
int N, K;
vector<vector<ll> > dp;
vector<pll> vec;
void f(int l, int r, int tl, int tr, int j) {
if(l > r) return ;
int tm = (l + r) / 2;
int p = tl;
for(int i=tl; i<=min(tm, tr); i++) {
ll v = dp[i-1][j-1] + (ll)(vec[tm].second - vec[i].first + 1) * (ll)(vec[tm].second - vec[i].first + 1);
v -= (ll)(max(0ll, vec[i-1].second - vec[i].first + 1)) * (ll)(max(0ll, vec[i-1].second - vec[i].first + 1));
if(v < dp[tm][j]) {
dp[tm][j] = v;
p = i;
}
}
f(l, tm-1, tl, p, j);
f(tm+1, r, p, tr, j);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
//d&c gl hf
vector<pll> P; P.push_back({ -1, -1 });
for(int i=0; i<n; i++) {
if(r[i] > c[i]) P.push_back({ c[i], r[i] });
else P.push_back({ r[i], c[i] });
}
sort(P.begin(), P.end(), [&](pll &a, pll &b) {
if(a.first == b.first) return a.second > b.second;
return a.first < b.first;
});
vector<pll> P2; P2.push_back(P[0]); P2.push_back(P[1]);
for(int i=2; i<=n; i++) {
if(P[i].first <= P2.back().second && P[i].second <= P2.back().second) continue;
P2.push_back(P[i]);
}
P = P2;
n = P.size() - 1;
N = n; K = k;
vec = P;
dp.resize(n+1, vector<ll>(k+1, 1e18));
dp[0][0] = 0;
for(int j=1; j<=k; j++)
f(1, n, 1, n, j);
return *min_element(dp[n].begin(), dp[n].end());
}
