#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<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);
}
v.push_back({0, 0});
for(int i = 1; i <= m + 1; i++) {
if(at[i]) {
if(!ats.empty() and ats.back() >= at[i]) {
continue;
}
ats.push_back(at[i]);
v.push_back({i, at[i]});
}
}
// ats.push_back(0);
// sort(ats.begin(), ats.end());
// ats.resize(unique(ats.begin(), ats.end()) - ats.begin());
// for(auto& [x, y] : v) {
// y = lower_bound(ats.begin(), ats.end(), y) - ats.begin();
// }
m = (int) v.size() - 1;
dp.resize(m + 1, vector<ll>(k + 1, 1e18));
for(int i = 0; i <= k; i++) {
dp[0][i] = 0;
}
for(int j = 1; j <= m; j++) {
for(int rem = k; rem >= 1; rem--) {
for(int i = j; i >= 1; i--) {
int prev = v[i - 1].second;
int x = v[i].first;
int y = v[j].second;
ll len = y - x;
ll inter = max(0, prev - x);
dp[j][rem] = min(dp[j][rem], dp[i - 1][rem - 1] + len * len - inter * inter);
}
}
}
ll ans = dp[m][k];
return ans;
}
