#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
using ll = long long;
const ll C = 2e6 + 10;
const ll N = 1e5 + 10;
const ll inf = 2e18;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i = 0;i<n;i++) {
if(r[i] > c[i]) {
swap(r[i], c[i]);
}
}
vector<pair<long long,long long>> v;
{
vector<pair<long long, long long>> d;
for(int i = 0;i<n;i++)d.push_back(make_pair(r[i], -c[i]-1));
sort(d.begin(), d.end());
for(int i = 0;i<n;i++)d[i].second*=-1;
long long mxr = -inf;
for(int i = 0; i<n; i++) {
if(d[i].second > mxr) {
v.push_back(make_pair(d[i].second, d[i].first));
mxr = d[i].second;
}
}
}
sort(v.begin(), v.end());
n = v.size();
long long dp[k+1][n+1];
for(int i = 0;i<=n;i++)dp[0][i] = inf;
for(int i = 0;i<=k;i++)dp[i][0] = 0;
for(int j = 1;j<=k;j++) {
for(int i = 1;i<=n;i++) {
long long mx = (v[i-1].first-v[i-1].second);
dp[j][i] = inf;
for(int z = i;z>=1;z--) {
mx = (long long)v[i-1].first-v[z-1].second;
long long val = dp[j-1][z-1]+mx*mx;
if(z!=1 and v[z-2].first > v[z-1].second) {
val-=(v[z-2].first-v[z-1].second)*(v[z-2].first-v[z-1].second);
}
dp[j][i] = min(dp[j][i], val);
}
}
}
return dp[k][n];
}
