#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int maxN = 5e2 + 20;
const long long inf = 1e18L + 20;
pair<int, int> ranges[maxN];
int L[maxN];
int R[maxN];
long long over[maxN];
long long dp[maxN][maxN];
int N, K;
long long take_photos(int _N, int M, int _K, vector<int> row, vector<int> col) {
N = _N;
K = _K;
for (int i = 1; i <= N; i++) {
if (row[i - 1] <= col[i - 1]) {
ranges[i].first = row[i - 1];
ranges[i].second = -col[i - 1];
}
else {
ranges[i].first = col[i - 1];
ranges[i].second = -row[i - 1];
}
}
sort(ranges + 1, ranges + N + 1);
int cnt = 0;
for (int i = 1; i <= N; i++) {
if (cnt == 0 || (L[cnt] != ranges[i].first && -ranges[i].second > R[cnt])) {
cnt++;
L[cnt] = ranges[i].first - 1;
R[cnt] = -ranges[i].second;
}
}
N = cnt;
for (int i = 2; i <= N; i++) {
if (R[i - 1] > L[i]) {
over[i] = 1LL * (R[i - 1] - L[i]) * (R[i - 1] - L[i]);
}
}
K = min(K, N);
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= K; j++) {
dp[i][j] = inf;
}
}
dp[0][0] = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= K; j++) {
for (int x = 1; x <= i; x++) {
dp[i][j] = min(dp[i][j], dp[x - 1][j - 1] + 1LL * (R[i] - L[x]) * (R[i] - L[x]) - over[x]);
}
}
}
return dp[N][K];
}
