#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int s, k;
vector<pair<ll,ll>> q;
vector<vector<ll>> dp;
void dnc(int kl, int l, int r, int optl, int optr){
if (l > r) return;
int mid = (l+r)/2;
int optmid;
for (int j=max(mid, optl); j<=optr; j++){
ll c = pow(q[j].second-q[mid].first+1, 2);
if (mid) c -= pow(max(0ll, q[mid-1].second-q[mid].first+1), 2);
if (c+dp[j+1][kl-1] < dp[mid][kl]){
dp[mid][kl] = c+dp[j+1][kl-1];
optmid = j;
}
}
dnc(kl, l, mid-1, optl, optmid);
dnc(kl, mid+1, r, optmid, optr);
}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
::k = k;
vector<pair<int,int>> p;
for (int i=0; i<n; i++) p.push_back({min(r[i], c[i]), -max(r[i], c[i])});
sort(p.begin(), p.end());
pair<int,int> prev = {-1, -1};
for (int i=0; i<n; i++){
if (prev.first <= p[i].first && -p[i].second <= prev.second) continue;
q.push_back({p[i].first, -p[i].second});
prev = {p[i].first, -p[i].second};
}
s = q.size();
dp.resize(s+1, vector<ll>(k+1, 1ll<<50));
for (int i=0; i<=k; i++) dp[s][i] = 0;
for (int kl=1; kl<=k; kl++) dnc(kl, 0, s-1, 0, s-1);
/*for (int i=0; i<=s; i++){
for (int kl=0; kl<=k; kl++) cout << dp[i][kl] << " ";
cout << endl;
}*/
return dp[0][k];
}
