#include "aliens.h"
#include <iostream>
#include <algorithm>
using namespace std;
struct node{
int x,y;
}a[1000005];
long long int dp[50005][105],x[100005],y[100005];
bool cmp(node a,node b)
{
return a.x<b.x;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;i++)
{
a[i].x=r[i];
a[i].y=c[i];
if(a[i].y<a[i].x)
{
swap(a[i].x,a[i].y);
}
}
sort(a,a+n,cmp);
long long int cnt=1;
x[1]=a[0].x;
y[1]=a[0].y;
for(int i=1;i<n;i++)
{
if(a[i].x>x[cnt] && a[i].y>y[cnt])
{
cnt++;
x[cnt]=a[i].x;
y[cnt]=a[i].y;
}
else if(a[i].x==x[cnt] && a[i].y>y[cnt])
{
x[cnt]=a[i].x;
y[cnt]=a[i].y;
}
}
n=cnt;
for(int i=1;i<=n;i++)
{
//cout<<x[i]<<" "<<y[i]<<endl;
}
for(int i=0;i<=n;i++)
{
for(int j=0;j<=k;j++)dp[i][j]=99999999999999999;
}
dp[0][0]=0;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=k;j++)
{
long long int nowy=y[i],nowx=x[i];
for(int l=i;l>=1;l--)
{
nowx=x[l];
dp[i][j]=min(dp[i][j],dp[l-1][j-1]+(nowy-nowx+1)*(nowy-nowx+1));
//cout<<i<<" "<<j<<" "<<dp[i][j]<<" "<<dp[l-1][j-1]<<" "<<nowx<<" "<<nowy<<endl;
}
}
}
long long int ans=10000000000000;
for(int i=0;i<=k;i++)
{
ans=min(dp[n][i],ans);
}
return ans;
}
