#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 ans[n+1][k+1];
for(int i=0;i<=n;i++)for(int j=0;j<=k;j++)ans[i][j]=LLONG_MAX;
ans[0][0]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=min(i,k);j++){
for(int past=0;past<i;past++){
if(ans[past][j-1]==LLONG_MAX)continue;
lint val=ans[past][j-1]
+(pts[i-1].second-pts[past].first+1)*(pts[i-1].second-pts[past].first+1)
-(past&&pts[past].first<=pts[past-1].second?
(pts[past-1].second-pts[past].first+1)*(pts[past-1].second-pts[past].first+1)
:0);
//cerr<<i<<" "<<j<<" "<<past<<" :: "<<val<<" "<<(pts[i-1].second-pts[past].first+1)*(pts[i-1].second-pts[past].first+1)<<"\n";
ans[i][j]=min(ans[i][j],val);
}
//cerr<<ans[i][j]<<" ";
}
//cerr<<"\n";
}
lint anss=LLONG_MAX;
for(int i=1;i<=k;i++){
anss=min(anss,ans[n][i]);
}
return anss;
}
