#include"aliens.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
vector<vector<ll>>dp;
pair<ll,ll>a[50005],b[50005];
bool cmp(pair<ll,ll>l,pair<ll,ll>r){
if(l.first==r.first)return l.second>r.second;
return l.first<r.first;
}
ll sq(ll a){
return a*a;
}
ll cost(ll l, ll r){
return sq(max(0ll,b[r].second-b[l].first+1))-sq(max(0ll,b[l-1].second-b[l].first+1));
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
dp.assign(n+5,vector<ll>(k+5,1e15));
dp[0][0]=0;
for(int i=0;i<n;i++)a[i+1]={min(r[i],c[i])+1,max(r[i],c[i])+1};
sort(a+1,a+1+n,cmp);
ll last=0,pos=0;
for(int i=1;i<=n;i++)
if(a[i].second>last){
last=a[i].second;
b[++pos]=a[i];
}
n=pos;
ll res=1e15;
for(int i=1;i<=k;i++){
for(int j=1;j<=n;j++)
for(int l=1;l<=j;l++)dp[j][i]=min(dp[j][i],dp[l-1][i-1]+cost(l,j));
res=min(res,dp[n][i]);
}
return res;
}
