#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
vector<ll>dp[100001];
const ll INF = 1e18;
ll take_photos(int n, int m, int K, vector<int> r, vector<int> c) {
vector<PII>tmp,p;
for(int i=0;i<n;i++)tmp.pb({min(r[i],c[i]),max(r[i],c[i])});
sort(all(tmp),[&](pii x,pii y){
if(x.fi==y.fi)return x.se > y.se;
return y.fi > x.fi;
});
int mx = 0;
for(pii x:tmp){
if(mx >= x.se)continue;
mx = max(mx,x.se);
p.pb(x);
}
sort(all(tmp),[&](pii x,pii y){
return y.se > x.se;
});
n = sz(p);
p.insert(p.begin(),{-1,-1});
for(int i=0;i<=n;i++)dp[i].assign(K+1,INF);
dp[0][0] = 0;
for(int i=1;i<=n;i++){
for(int j=0;j<i;j++){
for(int k=1;k<=K;k++){
ll x = (p[i].se - p[j+1].fi+1);
ll y = max(p[j].se - p[j+1].fi+1,0LL);
x*=x;
y*=y;
dp[i][k] = min(dp[i][k], dp[j][k-1] + x - y);
}
}
}
ll ans = INF;
for(int i=1;i<=K;i++)ans = min(ans,dp[n][i]);
return ans;
}
