#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<int> ats;
vector<ii> v;
vector<vector<vector<ll>>> dp;
ll f(int x, int last, int k) {
if(x >= m) {
return 0;
}
ll &r = dp[x][last][k];
if(r != -1) {
return r;
}
r = 1e18;
if(ats[last] >= ats[v[x].second]) {
r = min(r, f(x + 1, last, k));
}
if(k) {
// int mx = 0;
// for(int y = x; y < m; y++) {
// mx = max(mx, v[y].second);
// if(ats[mx] <= ats[last]) {
// continue;
// }
// ll len = ats[mx] - v[x].first;
// ll prev_len = max(0, ats[last] - v[x].first);
// r = min(r, f(x + 1, mx, k - 1) + len * len - prev_len * prev_len);
// }
int mx = 0;
int y = last + 1;
if(ats[v[x].second] > ats[last]) {
y = v[x].second;
}
for(; y < (int) ats.size(); y++) {
ll len = ats[y] - v[x].first;
ll prev_len = max(0, ats[last] - v[x].first);
r = min(r, f(x + 1, y, k - 1) + len * len - prev_len * prev_len);
}
}
// printf("x = %d last = %d k = %d r = %lld\n", x, last, k, 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);
}
ats.push_back(0);
for(int i = 1; i <= m + 1; i++) {
if(at[i]) {
ats.push_back(at[i]);
}
}
sort(ats.begin(), ats.end());
ats.resize(unique(ats.begin(), ats.end()) - ats.begin());
for(int i = 1; i <= m + 1; i++) {
if(at[i]) {
at[i] = lower_bound(ats.begin(), ats.end(), at[i]) - ats.begin();
v.push_back({i, at[i]});
}
}
m = (int) v.size();
dp.resize(m + 1, vector<vector<ll>>((int) ats.size() + 1, vector<ll>(k + 1, -1)));
ll ans = f(0, 0, k);
return ans;
}
