#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
ll sq(ll x){return x*x;}
ll take_photos(int n, int m, int k, vector<int> r, vector<int> c){
m--; // suppress warning
vector<pair<int, int>> v;
for(int i = 0; i < n; i++){
v.emplace_back(min(r[i], c[i]), -max(r[i], c[i]));
}
sort(v.begin(), v.end());
vector<pair<ll, ll>> a;
for(int i = 0; i < n; i++){
if(a.empty() || a.back().second < -v[i].second) a.emplace_back(v[i].first, -v[i].second);
}
n = (int)a.size();
vector<ll> dp(n, INF);
for(int h = 0; h < k; h++){
vector<ll> dp2(n);
for(int i = 0; i < n; i++){
dp2[i] = sq(a[i].second-a[0].first+1);
for(int j = 0; j < i; j++){
ll cost = sq(a[i].second-a[j+1].first+1) - sq(max(0ll, a[j].second-a[j+1].first+1));
dp2[i] = min(dp2[i], dp[j]+cost);
}
}
dp = dp2;
}
return dp[n-1];
}
