#include "aliens.h"
#include<algorithm>
#include<iostream>
#include<vector>
#include<stdio.h>
using namespace std;
#define INF 1000000000000000000
typedef pair<long long int,long long int> pii;
vector<pair<long long int,long long int> >arr;
long long int DP[5000][5000];
long long int cost[5000][5000];
int p;
long long sq2(long long x){
if(x>0)return x*x;
return 0;
}
bool cmp(pii a, pii b){
if(a.first==b.first){
if(a.second>b.second)return true;
return false;
}
if(a.first<b.first)return true;
return false;
}
long long int min(long long int a, long long int b){
if(a<b)return a;
return b;
}
long long take_photos(int n, int m, int k, vector<int> r,vector<int> c) {
pair<long long int,long long int>points[n];
for(int i=0;i<n;i++){
points[i]=pair<long long int,long long int>(r[i],c[i]);
if(r[i]>c[i])swap(points[i].first,points[i].second);
}
sort(points,points+n,cmp);
long long int cnt=-1;
for(int i=0;i<n;i++){
if(points[i].second>cnt){
cnt=points[i].second;
arr.push_back(points[i]);
//printf("%lld %lld \n",points[i].first,points[i].second);
}
}
p=arr.size();
for(int i=0;i<p;i++){
for(int j=i;j<p;j++){
cost[i][j]=points[j].second-points[i].first+1;
cost[i][j]*=cost[i][j];
if(i>0){
cost[i][j]-=sq2(points[i-1].second-points[i].first+1);
}
//cout<<cost[i][j]<<" ";
}//cout<<endl;
}
for(int i=0;i<=k;i++){
for(int j=0;j<=p;j++){
DP[j][i]=INF;
}
}
DP[0][0]=0;
for(int photo=1;photo<=k;photo++){
for(int i=1;i<=p;i++){
for(int j=0;j<i;j++){
DP[i][photo]=min(DP[i][photo],DP[j][photo-1]+cost[j][i-1]);
}
}
}
long long int ans=INF;
for(int i=0;i<=k;i++)ans=min(ans,DP[p][i]);
/*for(int i=0;i<=k;i++){
for(int j=0;j<=p;j++){
if(DP[j][i]==INF)cout<<-1<<" ";
else cout<<DP[j][i]<<" ";
}cout<<endl;
}*/
return ans;
}
