#include "aliens.h"
#include <algorithm>
#include <deque>
using namespace std;
struct A
{
long long a;
long long b;
}Node[100005],ttt[100005];
bool ok[100005]={0};
long long DP[100005];
long long con[100005]={0};
long long tt[100005];
deque < pair < pair < long long , long long > , long long > > L;
bool cmp(A a,A b)
{
return a.b<b.b||a.b==b.b&&a.a>b.a;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
long long i,j,N=0,ll,rr,ans=1e18,mid,l1,l2,r1,r2;
pair < pair < long long , long long >, long long > x,y,z;
for(i=0;i<n;i++)
{
ttt[i].a=(long long) max(r[i],c[i]);
ttt[i].b=(long long) min(r[i],c[i]);
}
sort(ttt,ttt+n,cmp);
ll=ttt[0].b;
rr=ttt[0].a;
for(i=1;i<n;i++)
{
if(ll<=ttt[i].b&&ttt[i].a<=rr) ok[i]=1;
else
{
ll=ttt[i].b;
rr=ttt[i].a;
}
}
for(i=0;i<n;i++) if(!ok[i]) Node[N++]=ttt[i];
sort(Node,Node+N,cmp);
Node[N].b=1e9;
tt[N]=1e9;
for(i=N-1;i>=0;i--) tt[i]=min(tt[i+1],Node[i].b);
ll=0;
rr=(long long) m*(long long) m;
//printf("%lld %lld\n",ll,rr);
while((rr-ll)>1)
{
mid=(rr+ll)/2;
L.clear();
for(j=0;j<N;j++)
{
DP[j]=1e18;
if(j==0) z=make_pair(make_pair(-2*Node[j].b,(Node[j].b)*Node[j].b),(long long) 0);
else z=make_pair(make_pair(-2*Node[j].b,DP[j-1]+(Node[j].b)*Node[j].b),con[j-1]);
if(!L.empty())
{
x=L.back();
L.pop_back();
while(!L.empty()&&((double) (z.first.first-x.first.first)/(double) (x.first.second-z.first.second))>=((double) (L.back().first.first-x.first.first)/(double) (x.first.second-L.back().first.second)))
{
x=L.back();
L.pop_back();
}
L.push_back(x);
}
if(L.empty()||L.back().first.first!=z.first.first) L.push_back(z);
x=L.front();
L.pop_front();
while(!L.empty()&&x.first.first*(Node[j].a+1)+x.first.second>=L.front().first.first*(Node[j].a+1)+L.front().first.second)
{
x=L.front();
L.pop_front();
}
L.push_front(x);
DP[j]=x.first.first*(Node[j].a+1)+x.first.second;
DP[j]+=(Node[j].a+1)*(Node[j].a+1);
DP[j]-=max((long long) 0,Node[j].a-Node[j+1].b+1)*max((long long) 0,Node[j].a-Node[j+1].b+1);
DP[j]+=mid;
con[j]=x.second+1;
}
if(con[N-1]<k) rr=mid;
else ll=mid;
}
L.clear();
for(j=0;j<N;j++)
{
DP[j]=1e18;
if(j==0) z=make_pair(make_pair(-2*Node[j].b,(Node[j].b)*Node[j].b),(long long) 0);
else z=make_pair(make_pair(-2*Node[j].b,DP[j-1]+(Node[j].b)*Node[j].b),con[j-1]);
if(!L.empty())
{
x=L.back();
L.pop_back();
while(!L.empty()&&((double) (z.first.first-x.first.first)/(double) (x.first.second-z.first.second))>=((double) (L.back().first.first-x.first.first)/(double) (x.first.second-L.back().first.second)))
{
x=L.back();
L.pop_back();
}
L.push_back(x);
}
if(L.empty()||L.back().first.first!=z.first.first) L.push_back(z);
x=L.front();
L.pop_front();
while(!L.empty()&&x.first.first*(Node[j].a+1)+x.first.second>=L.front().first.first*(Node[j].a+1)+L.front().first.second)
{
x=L.front();
L.pop_front();
}
L.push_front(x);
DP[j]=x.first.first*(Node[j].a+1)+x.first.second;
DP[j]+=(Node[j].a+1)*(Node[j].a+1);
DP[j]-=max((long long) 0,Node[j].a-Node[j+1].b+1)*max((long long) 0,Node[j].a-Node[j+1].b+1);
DP[j]+=ll;
con[j]=x.second+1;
}
if(con[N-1]==k) return DP[N-1]-ll*con[N-1];
l1=DP[N-1]-ll*con[N-1];
l2=con[N-1];
L.clear();
for(j=0;j<N;j++)
{
DP[j]=1e18;
if(j==0) z=make_pair(make_pair(-2*Node[j].b,(Node[j].b)*Node[j].b),(long long) 0);
else z=make_pair(make_pair(-2*Node[j].b,DP[j-1]+(Node[j].b)*Node[j].b),con[j-1]);
if(!L.empty())
{
x=L.back();
L.pop_back();
while(!L.empty()&&((double) (z.first.first-x.first.first)/(double) (x.first.second-z.first.second))>=((double) (L.back().first.first-x.first.first)/(double) (x.first.second-L.back().first.second)))
{
x=L.back();
L.pop_back();
}
L.push_back(x);
}
if(L.empty()||L.back().first.first!=z.first.first) L.push_back(z);
x=L.front();
L.pop_front();
while(!L.empty()&&x.first.first*(Node[j].a+1)+x.first.second>=L.front().first.first*(Node[j].a+1)+L.front().first.second)
{
x=L.front();
L.pop_front();
}
L.push_front(x);
DP[j]=x.first.first*(Node[j].a+1)+x.first.second;
DP[j]+=(Node[j].a+1)*(Node[j].a+1);
DP[j]-=max((long long) 0,Node[j].a-Node[j+1].b+1)*max((long long) 0,Node[j].a-Node[j+1].b+1);
DP[j]+=(ll+1);
con[j]=x.second+1;
}
if(con[N-1]==k) return DP[N-1]-(ll+1)*con[N-1];
r1=DP[N-1]-(ll+1)*con[N-1];
r2=con[N-1];
if(r2==l2) return r1;
return l1+(r1-l1)*(k-l2)/(r2-l2);
}
