#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
long long* dp[4005];
int n;
vector<pair<int,int> > its;
void computeDP(int lv, int l, int r, int ll = 0, int rr = n){
if(l > r) return;
int m = (l+r)/2;
int midx = -1;
long long mn = 1e18;
for(int bck = ll; bck <= min(m-1, rr); bck++){
int sl = its[m].second - its[bck+1].first + 1;
int il = max(its[bck].second - its[bck+1].first + 1, 0);
long long cval = dp[lv-1][bck] + 1ll * sl * sl - 1ll * il * il;
if(cval < mn){
mn = cval;
midx = bck;
}
}
dp[lv][m] = mn;
computeDP(lv, l, m-1, ll, midx);
computeDP(lv, m+1, r, midx, rr);
}
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
::n = n;
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]);
}
its = vector<pair<int,int> >(itvs.begin(), itvs.end());
n = its.size();
for(int i = 0; i <= k; i++){
dp[i] = new long long[n+5];
fill(dp[i], dp[i]+n+5, (long long)1e18);
}
its.insert(its.begin(), make_pair(-1,-1));
long long ans = 1e18;
dp[0][0] = 0ll;
for(int j = 1; j <= k; j++){
computeDP(j, 1, n);
ans = min(ans, dp[j][n]);
}
return ans;
}
