#include"aliens.h"
#include<bits/stdc++.h>
#ifdef EVAL
#else
#include"grader.cpp"
#endif
using namespace std;
typedef long long ll;
vector<vector<ll>>dp;
pair<ll,ll>a[50005],b[50005];
bool cmp(pair<ll,ll>l,pair<ll,ll>r){
if(l.first==r.first)return l.second>r.second;
return l.first<r.first;
}
ll sq(ll a){
return a*a;
}
ll cost(ll l, ll r){
return sq(max(0ll,b[r].second-b[l].first+1))-sq(max(0ll,b[l-1].second-b[l].first+1));
}
void divide(int l,int r,int optl,int optr,int k){
if(l>r)return;
int mid=(l+r)>>1,opt=0;
for(int i=optl;i<=optr;i++)
if(dp[mid][k]>dp[i-1][k-1]+cost(i,mid)){
dp[mid][k]=dp[i-1][k-1]+cost(i,mid);
opt=i;
}
divide(l,mid-1,optl,opt,k);
divide(mid+1,r,opt,optr,k);
}
ll take_photos(int n,int m,int k,vector<int>r,vector<int>c){
dp.assign(n+5,vector<ll>(k+5,1e15));
dp[0][0]=0;
for(int i=0;i<n;i++)a[i+1]={min(r[i],c[i])+1,max(r[i],c[i])+1};
sort(a+1,a+1+n,cmp);
ll last=0,pos=0;
for(int i=1;i<=n;i++)
if(a[i].second>last){
last=a[i].second;
b[++pos]=a[i];
}
n=pos;
for(int i=1;i<=n;i++)dp[i][1]=cost(1,i);
for(int i=2;i<=k;i++)divide(1,n,1,n,i);
ll res=1e15;
for(int i=1;i<=k;i++)res=min(res,dp[n][i]);
return res;
}
