#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define fi first
#define se second
#define mp make_pair
const int N = 4010;
ll dp[N][N];
ll sq(ll x){
return x * 1ll * x;
}
vector<pii> ff;
ll cost(int k, int i, int j){
return dp[i - 1][k - 1] + sq(ff[j].se - ff[i].fi + 1) - sq(max(0, ff[i - 1].se - ff[i].fi + 1));
}
void solve(int ki, int cl, int cr, int optl, int optr){
if(cl > cr) return;
int mid = (cl + cr) / 2;
int opt = optl;
ll cur = (ll)2e18;
ll chk;
for(int j = optl; j <= min(mid, optr); j ++ ){
chk = cost(ki, j, mid);
if(chk < cur){
cur = chk;
opt = j;
}
}
dp[mid][ki] = cur;
solve(ki, cl, mid - 1, optl, opt);
solve(ki, mid + 1, cr, opt, optr);
}
ll take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
vector<pii> segm;
for(int i = 0 ; i < n; i ++ ){
segm.push_back(mp(min(r[i],c[i]), max(r[i],c[i])));
}
sort(segm.begin(), segm.end(), [&](pii A, pii B){
if(A.fi == B.fi) return A.se > B.se;
else return A.fi < B.fi;
});
int big = -1;
ff.push_back(mp(-1,-1));
for(int i = 0 ; i < segm.size(); i ++ ){
if(segm[i].se > big){
ff.push_back(segm[i]);
big = segm[i].se;
}
}
int t = ff.size();
for(int i = 0 ; i < t; i ++) {
for(int j = 0 ; j <= k ; j ++ ){
dp[i][j]=(ll)1e18;
}
}
dp[0][0]=0;
ll ans = (ll)1e18;
for(int j = 1; j <= k ; j ++ ){
/*
for(int r = 1; r < t; r ++ ){
for(int l = r; l > 0; l -- ){
dp[r][j]=min(dp[r][j], dp[l - 1][j - 1] + sq(ff[r].se - ff[l].fi + 1) - sq(max(0, ff[l - 1].se - ff[l].fi + 1)));
}
}
*/
solve(j, 1, n, 1, n);
ans = min(ans, dp[t - 1][j]);
}
return ans;
}
