#include<iostream>
#include<algorithm>
#include<vector>
#include"aliens.h"
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define chmin(a,b) a=min(a,b)
#define chmax(a,b) a=max(a,b)
#define N 510
vector<ll> l,r;
ll take_photos(int n,int m,int k,vector<int> R,vector<int> C){
vector<P> v;
for(int i=0;i<n;i++){
if(R[i]>C[i])swap(R[i],C[i]);
v.push_back(make_pair((ll)R[i],(ll)C[i]));
}
sort(v.begin(),v.end());
ll rnd=-1;
l.push_back(-1); r.push_back(-1);
for(auto p:v){
ll x=p.first,y=p.second+1;
if(y<=rnd)continue;
rnd=y;
l.push_back(x);
r.push_back(y);
//cout<<"#"<<l.back()<<" "<<r.back()<<endl;
}
n=l.size()-1; //cout<<n<<endl;
ll dp[N][N];
for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)dp[i][j]=1e17;
dp[0][0]=0;
for(int i=0;i<=n;i++)for(int j=0;j<=k;j++){
//cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
for(int t=i+1;t<=n;t++){
ll cost=dp[i][j]+(r[t]-l[i+1])*(r[t]-l[i+1]);
ll x=max(0LL,r[i]-l[i+1]); cost-=x*x;
chmin(dp[t][j+1],cost);
}
}
ll ans=1e17;
for(int j=0;j<=k;j++)chmin(ans,dp[n][j]);
return ans;
}
