#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define dbgv(v) cout<<#v<<" = "; f(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define dbga(a,x,y) cout<<#a<<" = "; f(i,x,y) cout<<a[i]<<" "; cout<<endl
#define erorp(x) cout<<#x<<"={"<<x.F<<" , "<<x.S<<"}"<<endl
#define eror(x) cout<<#x<<'='<<(x)<<endl
#define f_(i,a,b) for(int i=a;i>=b;i--)
#define f(i,a,b) for(int i=a;i<b;i++)
#define nb(x) __builtin_popcount(x)
#define all(v) v.begin(),v.end()
#define bit(n,k) (((n)>>(k))&1)
#define Add(x,y) x=(x+y)%mod
#define maxm(a,b) a=max(a,b)
#define minm(a,b) a=min(a,b)
#define lst(x) x[x.size()-1]
#define sz(x) int(x.size())
#define mp make_pair
#define ll long long
#define pb push_back
#define S second
#define F first
const int N=50500,K=111;
const ll inf=1e15;
int n,m,k,A[N],B[N],rem[N];
ll ans,dp[N][K];
ll cost(int i,int j){
ll res=B[j]-A[i]+1;
return res*res;
}
ll G(int x){
if(x==1) return 0;
ll res=B[x-1]-A[x]+1;
if(res<=0) return 0;
return res*res;
}
void solve(int l,int r,int s,int e,int x){
if(r<=l) return ;
//cout<<l<<" "<<r<<" "<<s<<" "<<e<<" "<<x<<endl;
int mid=(l+r)>>1,p=s;
f(i,s,min(e,mid+1)){
if(dp[i-1][x-1]+cost(i,mid)-G(i)<dp[mid][x]){
dp[mid][x]=dp[i-1][x-1]+cost(i,mid)-G(i);
p=i;
}
}
solve(l,mid,s,p+1,x);
solve(mid+1,r,p,e,x);
}
void edame(){
minm(k,n);
f(i,1,n+1) f(j,0,k+1) dp[i][j]=inf;
f(i,1,k+1){
solve(1,n+1,1,n+1,i);
//cout<<i<<" -> "<<endl;
//cout<<"dp : ";
//f(j,1,n+1) cout<<dp[j][i]<<" ";
//cout<<endl;
}
ans=dp[n][k];
}
ll take_photos(int _n,int _m,int _k,vector<int> r,vector<int> c) {
n=_n,m=_m,k=_k;
f(i,0,n) if(r[i]>c[i]) swap(r[i],c[i]);
vector<int> vec(n);
iota(all(vec),0);
sort(all(vec),[&](int u,int v){ return r[u]+c[u]<r[v]+c[v]; });
int mx=-1,mn=m+1;
f(i,0,vec.size()){
if(mx>c[vec[i]]) rem[i]=1;
maxm(mx,c[vec[i]]);
}
f_(i,vec.size()-1,0){
if(mn<r[vec[i]]) rem[i]=1;
minm(mn,r[vec[i]]);
}
n=0;
f(i,0,vec.size()){
if(rem[i]) continue ;
n++;
A[n]=r[vec[i]];
B[n]=c[vec[i]];
}
edame();
return ans;
}
