#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long dp[4005][4005];
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
set<pair<int,int> > itvs;
for(int i = 0; i < n; i++){
if(c[i] < r[i]) swap(r[i], c[i]);
auto it = itvs.lower_bound({r[i], 0});
if(it != itvs.begin()){
--it;
if(it->second >= c[i]) continue; // this lies inside some intervals
++it;
}
if(it != itvs.end() && it->first == r[i] && it->second >= c[i]) continue; // this lies inside some intervals
while(it != itvs.end() && r[i] <= it->first && it->second <= c[i]){
it = itvs.erase(it);
}
itvs.emplace(r[i], c[i]);
}
vector<pair<int,int> > its(itvs.begin(), itvs.end());
n = its.size();
for(int i = 1; i < n; i++){
if(its[i-1].first >= its[i].first) while(true);
if(its[i-1].second >= its[i].second) while(true);
}
its.insert(its.begin(), make_pair(-1,-1));
long long ans = 1e18;
for(int i = 1; i <= n; i++) dp[0][i] = 1e18;
for(int j = 1; j <= k; j++){
for(int i = 1; i <= n; i++){
dp[j][i] = 1e18;
for(int bck = 0; bck < i; bck++){
int sl = its[i].second - its[bck+1].first + 1;
int il = max(its[bck].second - its[bck+1].first, 0);
dp[j][i] = min(dp[j][i], dp[j-1][bck] + 1ll * sl * sl - 1ll * il * il);
}
}
ans = min(ans, dp[j][n]);
}
return ans;
}
