// #include "aliens.h"
// #include <bits/stdc++.h>
// using namespace std;
// typedef long long ll;
// const int MAXN = 50000;
// const int MAXK = 4000;
// const ll INFLL = 1e18;
// vector<vector<ll>> dp;
// pair<int, int> all[MAXN];
// vector<pair<ll, ll>> lines[MAXK];
// void add(pair<ll, ll> l, int ops) {
// }
// ll query(ll x, int ops) {
// }
// ll take_photos(int n, int m, int k, vector<int> rows, vector<int> cols) {
// for (int i=0; i<n; i++) {
// if (rows[i] > cols[i])
// swap(rows[i], cols[i]);
// all[i] = {rows[i], -cols[i]};
// }
// sort(all, all+n);
// for (int i=0; i<n; i++) all[i].second = -all[i].second;
// vector<ll> l{-1}, r{-1}; int mx = -1;
// for (int i=0, N = n; i<N; i++) {
// if (i > 0 and all[i].first == all[i-1].first) {
// n--;
// continue;
// }
// if (all[i].second <= mx) {
// n--;
// continue;
// }
// l.push_back(all[i].first);
// r.push_back(all[i].second);
// mx = all[i].second;
// }
// // for (int i=1; i<=n; i++) cout << l[i] << ' ' << r[i] << '\n';
// // cout << '\n';
// dp = vector<vector<ll>> (n+1, vector<ll> (k+1, INFLL));
// // dp[0][0] = 0;
// // TODO: base
// for (int i=1; i<=n; i++) {
// dp[i][1] = (r[i] - l[1] + 1) * (r[i] - l[1] + 1);
// for (int ops=2; ops<=k; ops++) {
// dp[i][ops] = min(
// dp[i][ops-1],
// query(2 * r[i], ops-1) + r[i] * r[i] + 2 * r[i] - 1
// );
// ll delta = max(0LL, i > 0 ? r[i-1] - l[i] + 1 : 0LL);
// add({-l[i], 2 * l[i] - l[i] * l[i] - delta * delta + dp[i][ops]}, ops);
// }
// }
// return dp[n][k];
// }
#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 500;
const ll INFLL = 1e18;
ll dp[MAXN+1][MAXN+1];
pair<int, int> all[MAXN];
ll take_photos(int n, int m, int k, vector<int> rows, vector<int> cols) {
for (int i=0; i<n; i++) {
if (rows[i] > cols[i])
swap(rows[i], cols[i]);
all[i] = {rows[i], -cols[i]};
}
sort(all, all+n);
for (int i=0; i<n; i++) all[i].second = -all[i].second;
vector<ll> l{-1}, r{-1}; int mx = -1;
for (int i=0, N = n; i<N; i++) {
if (i > 0 and all[i].first == all[i-1].first) {
n--;
continue;
}
if (all[i].second <= mx) {
n--;
continue;
}
l.push_back(all[i].first);
r.push_back(all[i].second);
mx = all[i].second;
}
// for (int i=1; i<=n; i++) cout << l[i] << ' ' << r[i] << '\n';
// cout << '\n';
for (int i=1; i<=n; i++) dp[i][0] = INFLL;
for (int i=1; i<=n; i++) {
dp[i][1] = (r[i] - l[1] + 1) * (r[i] - l[1] + 1);
for (int ops=2; ops<=k; ops++) {
dp[i][ops] = dp[i][ops-1];
// cout << i << ':';
for (int j=i; j>=1; j--) {
ll res = dp[j-1][ops-1];
res += (r[i] - l[j] + 1) * (r[i] - l[j] + 1);
// if (i == 2 and j == 2) cout << (r[j-1] - l[j] + 1) << endl;
if (j > 1 and (r[j-1] - l[j] + 1) > 0)
res -= (r[j-1] - l[j] + 1) * (r[j-1] - l[j] + 1);
// cout << res << ' ';
dp[i][ops] = min(dp[i][ops], res);
}
// cout << '\n';
}
}
return dp[n][k];
}
