#include<bits/stdc++.h>
#include "aliens.h"
using namespace std;
long long a,b,c,d,e,i,j,ii,jj,zx,xc,M,K,pi,dp[4005][4005],pr[1000009],pas;
pair <long long, long long> p[1000009],pp[1000009];
long long take_photos(int Nn, int Mm, int Kk, std::vector<int> Rr, std::vector<int> Cc) {
M=Nn;a=Mm;K=Kk;
for(i=1; i<=M; i++){
if(Rr[i-1]>Cc[i-1]) swap(Rr[i-1],Cc[i-1]);
pp[i]={Rr[i-1]+1,-Cc[i-1]-1};
}
sort(pp+1,pp+M+1);
for(i=1; i<=M; i++) pp[i].second=-pp[i].second;
for(i=1; i<=M; i++){
if(pi!=0&&p[pi].second>=pp[i].second){
}else{
pi++;p[pi]=pp[i];
}
}
/*cout<<"rewrew "<<pi<<"\n";
for(i=1; i<=pi; i++) cout<<p[i].first<<" "<<p[i].second<<"\n";*/
for(i=1; i<=pi; i++){
pr[p[i].first]=p[i].second;
}
for(i=1; i<=a; i++){
pr[i]=max(pr[i],pr[i-1]);
}
for(i=0; i<=a+1; i++){
for(j=0; j<=K+1; j++){
dp[i][j]=a*a+3;
}
}
dp[0][0]=0;
for(i=1; i<=a; i++){
for(j=1; j<=min(i,K); j++){
dp[i][j]=i*i;
for(ii=0; ii<i; ii++){
zx=i*i+i*(-2*ii)+(dp[pr[ii]][j-1]-pr[ii]*pr[ii]+2*pr[ii]*ii);
dp[i][j]=min(dp[i][j],zx);
}
}
}
pas=dp[a][1];
for(j=1; j<=K; j++){
pas=min(pas,dp[a][j]);
}
return pas;
}
