#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
#define fi first
#define se second
long long D[109][100009];
long long DP(vector<pii>& A, int K) {
int N = A.size(); K = min(K, N);
for(int i=0; i<=K; i++) for(int j=0; j<N; j++) D[i][j] = 1LL * 1e18;
for(int i=0; i<N; i++) D[1][i] = 1LL * (A[i].se - A[0].fi + 1) * (A[i].se - A[0].fi + 1);
for(int i=2; i<=K; i++) {
for(int j=0; j<N; j++) {
for(int k=0; k<j; k++) {
D[i][j] = min(D[i][j], D[i-1][k] + 1LL * (A[j].se - A[k+1].fi + 1) * (A[j].se - A[k+1].fi + 1) - max(0LL, 1LL * (A[k].se - A[k+1].fi + 1) * (A[k].se - A[k+1].fi + 1)));
}
}
}
return D[K][N-1];
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
vector<pii> A, B;
for(int i=0; i<n; i++) {
if(r[i] > c[i]) swap(r[i], c[i]);
A.push_back({r[i], c[i]});
}
sort(A.begin(), A.end(), [&](pii P, pii Q) {
if(P.se == Q.se) return P.fi > Q.fi;
return P.se < Q.se;
});
for(int i=0; i<n; i++) {
while(B.size() && B.back().fi >= A[i].fi) B.pop_back();
B.push_back(A[i]);
}
return DP(B, k);
}
