#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
const int MAXN=1e5+10;
typedef long long ll;
ll INF=1e18;
int n,m,k;
ll dp[MAXN];
int cnt[MAXN];
pair <ll,ll> d[MAXN];
vector <pair <int,int>> aux,v;
bool cmp (pair <ll,ll> a, pair <ll,ll> b){
if (a.first==b.first) return a.second>b.second;
return a.first<b.first;
}
ll f (pair <ll,ll> d, ll x){
return d.first*x+d.second;
}
bool g (ll i, ll j, ll x){
///daca j <= i atunci scot i
if (f (d[i],x)>f (d[j],x)) return true;
if (f (d[i],x)<f (d[j],x)) return false;
return cnt[i]>=cnt[j];
}
ll solve (ll x){
dp[0]=cnt[0]=0;
for (int i=1;i<=n;++i){
dp[i]=INF;
cnt[i]=1e9;
}
deque <int> dq;
for (int i=0;i<=n;++i){
if (i){
dp[i]=1ll*v[i].second*v[i].second;
if (dq.empty ()){
cnt[i]=1;
}
else{
while (dq.size ()>=2){
int i1=dq.front ();
dq.pop_front ();
int i2=dq.front ();
dq.push_front (i1);
if (g (i1,i2,v[i].second)){
dq.pop_front ();
}
else
break;
}
int pcrt=dq.front ();
dp[i]+=f (d[pcrt],v[i].second);
cnt[i]=cnt[pcrt]+1;
}
}
if (i<=n-1){
ll acrt=-2*(v[i+1].first-1);
ll bcrt=dp[i]+1LL*(v[i+1].first-1)*(v[i+1].first-1)+x;
ll aux=max (0,v[i].second-v[i+1].first+1);
aux*=aux;
bcrt-=aux;
d[i]={acrt,bcrt};
while (dq.size ()>=2){
int i1=dq.back ();
dq.pop_back ();
int i2=dq.back ();
/**
x1=(d[i2].second-d[i1].second)/(d[i1].first-d[i2].first)
x2=(d[i2].second-d[i].second)/(d[i].first-d[i2].first)
**/
ll a=(d[i2].second-d[i1].second)*(d[i].first-d[i2].first);
ll b=(d[i1].first-d[i2].first)*(d[i2].second-d[i].second);
if (a>b or (a==b and cnt[i]<=cnt[i1])){
continue;
}
dq.push_back (i1);
break;
}
dq.push_back (i);
}
}
return cnt[n];
}
ll take_photos (int N, int M, int K, vector <int> r, vector <int> c){
n=N;
m=M;
k=K;
for (int i=0;i<n;++i){
r[i]++;
c[i]++;
if (r[i]>c[i]){
swap (r[i],c[i]);
}
aux.push_back ({r[i],c[i]});
}
sort (aux.begin (),aux.end (),cmp);
v.push_back ({0,0});
int cmax=0;
for (auto x:aux){
if (x.second>cmax){
cmax=x.second;
v.push_back (x);
}
}
n=v.size ()-1;
ll st=0,dr=1e12,rez;
while (st<=dr){
ll mij=(st+dr)/2;
if (solve (mij)>k){
st=mij+1;
}
else{
dr=mij-1;
rez=mij;
}
}
solve (rez);
return dp[n]-k*rez;
}
