#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]) {
// printf("x = %d last = %d k = %d\n", x, last, k);
r = min(r, f(x + 1, last, k));
}
if(k) {
for(int y = x + 1; y <= m + 1; y++) {
ll len = y - x;
r = min(r, f(x, y, k - 1) + len * len);
}
}
// printf("x = %d last = %d k = %d at = %d r = %lld\n", x, last, k, at[x], r);
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;
}
