#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
using lint=int64_t;
using pii=pair<lint,lint>;
#define pb push_back
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++){
if(c[i]<r[i]){
swap(c[i],r[i]);
}
}
int points[m+1];
memset(points,-1,sizeof(points));
for(int i=0;i<n;i++){
points[r[i]]=max(points[r[i]],c[i]);
}
vector<pii>pts;
for(int i=0;i<=m;i++){
if(points[i]!=-1){
if(!pts.size()||pts.back().second<points[i]){
pts.pb(pii{i,points[i]});
}
}
}
n=pts.size();
lint a[n],b[n],x[n],ans[n][k+1];
ans[0][1]=(pts[0].second-pts[0].first+1)*(pts[0].second-pts[0].first+1);
a[0]=-2*pts[0].first;
b[0]=-ans[0][1];
x[0]=pts[0].first*pts[0].first-2*pts[0].first;
for(int i=1;i<n;i++){
a[i]=-2*pts[i].first;
b[i]=-(pts[i].second-pts[i].first+1)*(pts[i].second-pts[i].first+1);
x[i]=pts[i].first*pts[i].first-2*pts[i].first;
lint y=(pts[i].second*pts[i].second)+2*pts[i].second+1;
ans[i][1]=(pts[i].second-pts[0].first+1)*(pts[i].second-pts[0].first+1);
for(int j=2;j<=min(i+1,k);j++){
ans[i][j]=ans[i-1][j-1]+(pts[i].second-pts[i].first+1)*(pts[i].second-pts[i].first+1);
if(pts[i].first<=pts[i-1].second){
ans[i][j]-=(pts[i-1].second-pts[i].first+1)*(pts[i-1].second-pts[i].first+1);
}
for(int past=0;past<i;past++){
ans[i][j]=min(ans[i][j],b[past]+x[past]+y+ans[past][j]+a[past]*pts[i].second);
//cerr<<"for "<<i<<" "<<j<<" extend "<<past<<" :: "<<b[past]+x[past]+y+ans[past][j-1]+a[past]*pts[i].second<<"\n";
//cerr<<"->> "<<b[past]<<" "<<x[past]<<" "<<y<<" "<<ans[past][j]<<" "<<a[past]*pts[i].second<<"\n";
}
}
/*
for(int j=1;j<=k;j++){
cerr<<ans[i][j]<<" ";
}
cerr<<"\n";
*/
}
//cerr<<b[0]<<"\n";
//cerr<<n<<"\n";
lint anss=LLONG_MAX;
for(int i=1;i<=min(k,n);i++){
anss=min(anss,ans[n-1][i]);
}
return anss;
}
