#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define N ((int)50*1000+100)
#define INF ((ll)1e18)
ll dp[2][N];
pair <int,int> a[N];
vector <pair<int,int> > b;
ll take_photos(int n, int m, int k,vector<int> r,vector<int> c)
{
for(int i=1;i<=n;i++)a[i]={min(r[i-1],c[i-1]),-max(r[i-1],c[i-1])};
sort(a+1,a+n+1);
int maxi=-1;
for(int i=1;i<=n;i++)
{
if(-a[i].second<=maxi){continue;}
maxi=-a[i].second;
b.push_back(a[i]);
}
n=b.size();
for(int i=1;i<=n;i++)a[i]=b[i-1],a[i].second*=-1;//,cout<<a[i].first<<" "<<a[i].second<<"\n";
dp[0][0]=0;
for(int i=1;i<N;i++)dp[0][i]=INF;
ll ans=INF;
a[0]={-100,-100};
for(int t=1;t<=k;t++)
for(int i=1;i<=n;i++)
{
dp[(t&1)][i]=INF;
for(int j=i;j>0;j--)
dp[(t&1)][i]=min(dp[(t&1)][i],dp[!(t&1)][j-1]+1LL*(a[i].second-a[j].first+1)*(a[i].second-a[j].first+1)-
1LL*(max(0,(a[j-1].second-a[j].first+1))*max(0,(a[j-1].second-a[j].first+1))));
if(i==n)ans=min(ans,dp[(t&1)][i]);
// cout<<t<<" "<<i<<" "<<dp[(t&1)][i]<<"\n";
}
return ans;
}
