#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define fi first
#define se second
typedef long long LL;
typedef pair<LL,LL> pii;
typedef pair<pii,LL> piii;
vector<pii> V,point;
vector<piii> line;
LL N,M,K,dp[100005],opt[100005];
bool cmpV(pii A,pii B){
if(A.fi!=B.fi)return A.fi<B.fi;
return A.se>B.se;
}
pii tpot(pii satu,pii dua){
pii jwb;
jwb.fi=dua.se-satu.se;
jwb.se=satu.fi-dua.fi;
return jwb;
}
bool cmp(pii a,pii b){
return a.fi*b.se<=a.se*b.fi;
}
LL sq(LL a){
return a*a;
}
LL F(LL penalty){
line.clear();
for(LL i=1;i<=N;i++){
LL x=V[i].se;
LL intersect;
if(V[i].first>V[i-1].second)intersect=0;
else intersect=sq(V[i-1].second-V[i].first+1);
piii now={{2*V[i].fi,-(V[i].fi*V[i].fi-2*V[i].fi+1-intersect+dp[i-1])},i-1};
LL skg=line.size()-1,prev=line.size()-2;
while(skg>0 && cmp(tpot(now.fi,line[skg].fi),tpot(now.fi,line[prev].fi))){
//hapus yang gamasuk hull
line.pop_back();
skg--;
prev--;
}
line.push_back(now);
LL ki=1,ka=(LL)line.size()-1,add=-1e18,id;
while(ki<=ka){
LL mid=(ki+ka)/2;
LL l=line[mid-1].fi.fi*x+line[mid-1].fi.se;
LL r=line[mid].fi.fi*x+line[mid].fi.se;
if(l>add){
add=l;
id=line[mid-1].se;
}
if(r>add){
add=r;
id=line[mid].se;
}
if(l>r)ka=mid-1;
else ki=mid+1;
}
if(line.size()==1){
add=line[0].fi.fi*x+line[0].fi.se;
id=line[0].se;
}
dp[i]=-add+sq(V[i].se)+2*V[i].se+penalty;
opt[i]=id;
}
LL noww=N,byk=0;
while(noww!=0){
byk++;
noww=opt[noww];
}
return byk;
}
LL take_photos(int n, int m, int k, vector<int> r, vector<int> c) {
N=(LL)n;M=(LL)m;K=(LL)k;
for(LL i=0;i<N;i++){
if(r[i]>c[i])swap(r[i],c[i]);
point.push_back(make_pair((LL)r[i],(LL)c[i]));
}
sort(point.begin(),point.end(),cmpV);
point.erase(unique(point.begin(),point.end()),point.end());
V.push_back(make_pair(-1,-1));
V.push_back(point[0]);
pii last=point[0];
for(LL i=1;i<N;i++){
if(point[i].se>last.se){
V.push_back(point[i]);
last=point[i];
}
}
N=V.size()-1;
K=min(K,N);
LL ki=0,ka=M*M,res;
while(ki<=ka){
LL mid=(ki+ka)/2;
if(F(mid)>K)ki=mid+1;
else{
res=mid;
ka=mid-1;
}
}
F(res);
res=dp[N]-res*k;
return res;
}
