#include "aliens.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int N,M,K;
ll dp[100005],c1=0,v1,c2=1e6,v2,cnt[100005];
struct tacka{
int x,y;/// X i Y su kao u matematici
} tniz[100005],niz[100005],tpp;
stack<tacka> S;
bool pox(tacka a,tacka b){
if(a.x<b.x)
return true;
if(a.x>b.x)
return false;
return a.y<b.y;
}
ll koliko(ll x,ll y){
ll r=abs(x-y);
ll d=r+1;
return d*d;
}
void izracunaj(ll lmb){
dp[0]=0;
cnt[0]=0;
for(int i=1;i<=N;i++){
dp[i]=dp[i-1]+koliko(niz[i].x,niz[i].y)-lmb;
cnt[i]=cnt[i-1]+1;
for(int j=i-1;j>=1;j--){
if(koliko(niz[i].x,niz[j].y)+dp[j-1]-lmb<dp[i]){
dp[i]=koliko(niz[i].x,niz[j].y)+dp[j-1]-lmb;
cnt[i]=cnt[j-1]+1;
}
}
}
if(cnt[N]<K and cnt[N]>c1){
c1=cnt[N];
v1=dp[N]+lmb*cnt[N];
}
if(cnt[N]>K and cnt[N]<c2){
c2=cnt[N];
v2=dp[N]+lmb*cnt[N];
}
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
N=n;
M=m;
K=k;
for(int i=1;i<=N;i++){
tniz[i].x=c[i-1]+1;
tniz[i].y=r[i-1]+1;
}
for(int i=1;i<=N;i++)
if(tniz[i].x<tniz[i].y)
swap(tniz[i].x,tniz[i].y);
sort(tniz+1,tniz+1+N,pox);
tpp.x=-1;
tpp.y=-1e9;
S.push(tpp);
// cout<<N<<endl;
//for(int i=1;i<=N;i++)
// cout<<tniz[i].x<<" "<<tniz[i].y<<endl;
for(int i=1;i<=N;i++){
if(S.top().x==tniz[i].x)
continue;
while(S.top().y>=tniz[i].y)
S.pop();
S.push(tniz[i]);
}
for(int i=1;i<=N;i++){
niz[i].x=0;
niz[i].y=0;
}
N=S.size()-1;
for(int i=N;i>=1;i--){
niz[i]=S.top();
S.pop();
}
//cout<<N<<endl;
//for(int i=1;i<=N;i++)
// cout<<niz[i].x<<" "<<niz[i].y<<endl;
if(K>=N){
ll res=0;
for(int i=1;i<=N;i++)
res+=koliko(niz[i].x,niz[i].y);
//cout<<"OVDE"<<endl;
return res;
}
ll dg=-1e13,gg=0,sred;
while(dg<=gg){
sred=(dg+gg)/2;
izracunaj(sred);
if(cnt[N]==K)
break;
if(cnt[N]<K)
dg=sred+1;
else
gg=sred-1;
}
return v1+((v2-v1)/(c2-c1))*(K-c1);
}
