#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
constexpr ll INF = 1000000000000000000LL;
ll n, m, q, k, x, y, a, b, c;
bool comp(pair<ll, ll> a, pair<ll, ll> b) {
return a.first + a.second < b.first + b.second;
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
// if (k == n) {
// set< pair<ll, ll> > st;
// for (int e = 0; e < n; e++) {
// for (int i = min(r[e], c[e]); i <= max(r[e], c[e]); i++) {
// for (int j = min(r[e], c[e]); j <= max(r[e], c[e]); j++) {
// st.insert({i, j});
// }
// }
// }
// return st.size();
// }
set< pair<ll, ll> > st;
for (int i = 0; i < n; i++) {
st.insert({min(r[i], c[i]), max(r[i], c[i])});
}
vector< pair<ll, ll> > v;
for (auto i : st) {
bool fl = 1;
for (auto j : st) {
if (i != j && i.first >= j.first && i.second <= j.second) {
fl = 0;
break;
}
}
if (fl) {
v.push_back(i);
}
}
sort(v.begin(), v.end(), comp);
n = v.size();
k = min(k, n);
ll num = 0;
set< pair<ll, ll> > st1;
for (int e = 0; e < n; e++) {
num += (v[e].second - v[e].first + 1) * (v[e].second - v[e].first + 1);
for (int i = v[e].first; i <= v[e].second; i++) {
for (int j = v[e].first; j <= v[e].second; j++) {
st1.insert({i, j});
}
}
}
num -= st1.size();
vector< vector<ll> > dp(k + 1, vector<ll> (n + 1, INF));
for (int i = 0; i <= k; i++) {
for (int j = 0; j <= n; j++) {
if (i == 0) {
if (j == 0) {
dp[i][j] = 0;
}
}
else {
for (int j1 = 1; j1 <= j; j1++) {
dp[i][j] = min(dp[i][j], (v[j - 1].second - v[j1 - 1].first + 1) * (v[j - 1].second - v[j1 - 1].first + 1) + dp[i - 1][j1 - 1]);
}
}
}
}
// cout << num << '\n';
return dp[k][n] - num;
}
