#include<bits/stdc++.h>
#include "aliens.h"
#define fi first
#define se second
using namespace std;
const long long INF=(long long)1e18+7;
const int N=1e5;
struct Interval
{
long long l,r;
Interval(int row=-1,int col=-1)
{
l=row;
r=col;
if(l>r)
swap(l,r);
return;
}
inline bool operator<(const Interval &oth) const
{
if(l==oth.l)
return r>oth.r;
return l<oth.l;
}
inline long long common(Interval oth)
{
if(oth.r<l || r<oth.l)
return 0;
if(oth.r>r)
return r-oth.l+1;
return oth.r-l+1;
}
inline long long size()
{
return r-l+1;
}
};
struct Ans
{
long long w,k;
Ans(long long _w=0,long long _k=0) : w(_w),k(_k) {}
};
struct Function
{
long long a,b;
int id;
Function(long long _a,long long _b,int _id) : a(_a),b(_b),id(_id) {}
inline long long f(long long x)
{
return x*x+a*x+b;
}
inline long long better(Function &oth)
{
if(oth.a==a)
return INF;
return (oth.b-b+a-oth.a)/(a-oth.a);
}
};
Interval tab[N+10];
long long dp[N+10];
int kk[N+10];
long long cross[N+10];
long long sub[N+10];
deque<Function> dq;
inline bool try_pop(int i)
{
if(dq.size()<2)
return false;
Function t=dq.front();
dq.pop_front();
if(dq.front().f(tab[i].r)<t.f(tab[i].r))
return true;
dq.push_front(t);
return false;
}
inline bool try_pop_back(Function &x)
{
if(dq.size()<2)
return false;
if(x.f(cross[dq.back().id])<dq.back().f(cross[dq.back().id]))
{
dq.pop_back();
return true;
}
return false;
}
inline void try_push(int i,long long c)
{
Function t(-2*(tab[i+1].l-1),dp[i]+c-sub[i+1]+(tab[i+1].l-1)*(tab[i+1].l-1),i);
while(try_pop_back(t));
if(!dq.empty())
cross[i]=t.better(dq.back());
dq.push_back(t);
return;
}
inline Ans solve(int n,long long c)
{
int i;
dq.clear();
dp[0]=0;
kk[0]=0;
try_push(0,c);
for(i=1;i<=n;i++)
{
while(try_pop(i));
kk[i]=kk[dq.front().id]+1;
dp[i]=dq.front().f(tab[i].r);
try_push(i,c);
}
return Ans(dp[n],kk[n]);
}
long long take_photos(int n,int m,int k,vector<int> r,vector<int> c)
{
int i,j;
long long ans=0;
for(i=1;i<=n;i++)
{
tab[i]=Interval(r[i-1],c[i-1]);
}
sort(tab+1,tab+n+1);
for(i=1,j=-1;i<=n;i++)
{
if(tab[i].r<=j)
tab[i].l=m+1;
j=max(j,(int)tab[i].r);
}
sort(tab+1,tab+n+1);
for(i=1;i<=n && tab[i].l<m;i++);
n=i-1;
tab[0]=Interval(-1,-1);
tab[n+1]=Interval(m+1,m+1);
if(n<=k)
{
for(i=1;i<=n;i++)
ans+=tab[i].size()*tab[i].size()-tab[i].common(tab[i-1])*tab[i].common(tab[i-1]);
return ans;
}
for(i=1;i<=n;i++)
{
sub[i]=tab[i].common(tab[i-1]);
sub[i]*=sub[i];
}
long long bg=0,en=(long long)m*m,mid;
while(bg<en)
{
mid=(bg+en)/2;
Ans tmp=solve(n,mid);
if(tmp.k<=k)
en=mid;
else
bg=mid+1;
}
Ans tmp=solve(n,bg);
return tmp.w-bg*k;
}
