#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;
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<ll> st;
for (int i = 0; i < n; i++) {
st.insert(r[i]);
}
vector<ll> v;
for (int i : st) {
v.push_back(i);
}
n = v.size();
vector< vector<ll> > dp(k + 1, vector<ll> (n + 1, INF));
for (int i = 0; i <= k; i++) {
for (int j = 1; 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] - v[j1 - 1] + 1) * (v[j - 1] - v[j1 - 1] + 1) + dp[i - 1][j1 - 1]);
}
}
}
}
return dp[k][n];
}
