#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int M = 1e6 + 5;
int n, m, k;
int at[M];
vector<ii> v;
vector<vector<vector<ll>>> dp;
ll f(int x, int last, int k) {
if(x > m + 1) {
return 0;
}
ll &r = dp[x][last][k];
if(r != -1) {
return r;
}
r = 1e18;
if(!at[x] or last >= at[x]) {
r = min(r, f(x + 1, last, k));
}
if(k) {
int mx = at[x];
for(int y = x + 1; y <= m + 2; y++) {
if(mx <= last) {
continue;
}
ll len = mx - x;
ll prev_len = max(0, last - x);
r = min(r, f(x + 1, mx, k - 1) + len * len - prev_len * prev_len);
mx = max(mx, at[y]);
}
}
return r;
}
ll take_photos(int nn, int mm, int kk, vector<int> r, vector<int> c) {
n = nn;
m = mm;
k = kk;
for(int i = 0; i < n; i++) {
if(r[i] > c[i]) {
swap(r[i], c[i]);
}
at[r[i] + 1] = max(at[r[i] + 1], c[i] + 2);
}
sort(v.begin(), v.end());
dp.resize(m + 2, vector<vector<ll>>(m + 2, vector<ll>(k + 1, -1)));
ll ans = f(1, 0, k);
return ans;
}
