#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF=1e18;
long long take_photos(int n, int m, int k, vector<int> r, vector<int> c){
vector<pair<ll,ll>> a;
for(ll i=0; i<n; i++){
if(c[i]<r[i]) swap(c[i],r[i]);
a.push_back({r[i],-c[i]});
}
r.clear();
c.clear();
sort(a.begin(),a.end());
r.push_back(a[0].first-1);
c.push_back(-a[0].second);
n=a.size();
ll x=-a[0].second;
// cout<<n<<endl;
for(ll i=1; i<n; i++){
// cout<<i<<endl;
if(-a[i].second>x){
r.push_back(a[i].first-1);
c.push_back(-a[i].second);
x=-a[i].second;
}
}
n=r.size();
// cout<<n<<endl;
ll ans[n+1][k+1];
for(ll i=0; i<n; i++){
ans[i][0]=(c[n-1]-r[i])*(c[n-1]-r[i]);
if(i>0 && c[i-1]>r[i]) ans[i][0]-=(c[i-1]-r[i])*(c[i-1]-r[i]);
}
for(ll x=0; x<=k; x++){
ans[n][x]=0;
}
for(ll x=1; x<=k; x++){
for(ll i=0; i<n; i++){
ans[i][x]=INF;
for(ll j=i; j<n; j++){
ans[i][x]=min(ans[i][x],(c[j]-r[i])*(c[j]-r[i])+ans[j+1][x-1]);
}
if(i>0 && c[i-1]>r[i]) ans[i][x]-=(c[i-1]-r[i])*(c[i-1]-r[i]);
}
}
return ans[0][k];
}
