#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define long long long
struct Point {
long r;
long c;
} p[50005], a[50005];
long maxc, plen;
long dp[4005][50005];
long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
for (long i = 0; i < n; i++) {
if (r[i] > c[i]) swap(r[i], c[i]);
p[i].r = r[i];
p[i].c = c[i];
}
sort(p, p + n,
[](const Point &a, const Point &b) {
return a.r < b.r || (a.r == b.r && a.c < b.c);
}
);
maxc = -1, plen = 0;
a[0].r = -100, a[0].c = -100;
for (long i = 0; i < n; i++) {
if (p[i].c > maxc) {
maxc = p[i].c;
a[++plen] = p[i];
}
}
n = plen;
for (long i = 0; i <= k; i++)
for (long j = 0; j <= n; j++)
dp[i][j] = 1e15;
dp[0][0] = 0;
long ans = 1e15;
for (long i = 1; i <= k; i++) {
for (long j = 1; j <= n; j++) {
for (long x = 0; x < j; x++) {
dp[i][j] = min(dp[i][j], dp[i - 1][x] +
(a[j].c - a[x + 1].r + 1) * (a[j].c - a[x + 1].r + 1) -
max(0ll, a[x].c - a[x + 1].r + 1) * max(0ll, a[x].c - a[x + 1].r + 1));
}
}
ans = min(ans, dp[i][n]);
}
return ans;
}
