#include <bits/stdc++.h>
#include "aliens.h"
using ll = long long;
using namespace std;
const int MAXN = 5e4 + 10;
const ll INF = 1e12 + 10;
ll inter[MAXN];
vector<vector<ll>> dp;
vector<pair<ll, ll>> c;
void compute(int k, int l, int r, int opt_min, int opt_max){
if(l > r) return;
int m = (l + r) / 2;
pair<ll, ll> best = {INF, 0};
for(int j=opt_min; j<=opt_max; j++){
ll cost = (c[m - 1].second - c[j].first + 1) * (c[m - 1].second - c[j].first + 1);
best = min(best, {dp[k - 1][j] + cost - inter[j], j});
}
dp[k][m] = best.first;
compute(k, l, m - 1, opt_min, best.second);
compute(k, m + 1, r, best.second, opt_max);
}
ll take_photos(int n, int m, int K, vector<int> l, vector<int> r){
dp.resize(K + 1, vector<ll> (n + 1));
c.clear();
vector<pair<ll, ll>> v;
for(int i=0; i<n; i++){
if(l[i] > r[i]) swap(l[i], r[i]);
v.push_back({l[i], r[i]});
}
sort(v.begin(), v.end());
ll max_r = -1;
for(auto [l, r] : v){
if(max_r < r){
if(max_r >= l){
if(!c.empty()){
inter[c.size()] = (max_r - l + 1) * (max_r - l + 1);
}
}
c.push_back({l, r});
max_r = r;
}
}
n = c.size();
dp[0][0] = 0;
for(int i=1; i<=n; i++) dp[0][i] = INF;
for(int k=1; k<=K; k++) compute(k, 1, n, 0, n - 1);
return dp[K][n];
}
