#include <bits/stdc++.h>
#include "aliens.h"
#define ll long long
#define pb push_back
#define mp make_pair
#define P pair<ll,ll>
using namespace std;
const int maxn = 4100;
ll dp[maxn][maxn];
int n, m, k;
vector<P>temp_segments, segments;
long long take_photos(int N, int M, int K, std::vector<int> r, std::vector<int> c) {
n = N; m = M; k = K;
for(int i=0;i<N;i++) {
temp_segments.pb(mp(min(r[i], c[i]), max(r[i], c[i])));
}
sort(temp_segments.begin(), temp_segments.end());
int li = -1, ri = -1;
for(auto i:temp_segments) {
if(i.first >= li && i.second <= ri) continue;
else {
segments.pb(i);
li = i.first;
ri = i.second;
}
}
for(int i=0;i<=n;i++) {
for(int j=0;j<=n;j++) {
dp[i][j] = (1LL << 45);
}
dp[i][0] = 0LL;
}
int n = segments.size();
for(int p=1;p<=min(n, k);p++) {
for(int i=1;i<=n;i++) {
dp[p][i] = LLONG_MAX;
for(int t=0;t<i;t++) {
ll intersection = 0LL;
ll cost = 0LL;
cost = segments[i-1].second - segments[t].first + 1;
cost *= cost;
if(t > 0) {
ll temp = segments[t-1].second - segments[t].first + 1;
intersection = max(0LL, temp) * max(0LL, temp);
}
dp[p][i] = min(dp[p][i], dp[p-1][t] + cost - intersection);
}
}
}
return dp[min(n, k)][n];
}
