#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
using i64=long long;
const i64 INF=1e18;
#define bug(x) cerr<<#x<<x<<'\n';
#define all(yy) yy.begin(),yy.end()
#define pb push_back
const int inf=1e9;
struct duo
{
int l,r;
bool operator <(const duo&b)const
{
if(l==b.l)
{
return r>b.r;
}
return l<b.l;
}
};
////////////////////////////GEOMETRY
////////////////////////////////////
struct line
{
i64 a,b;
i64 calculate(int x)
{
return a*x+b;
}
};
struct node
{
line a;
int k;
};
i64 intersect(const line& c,const line& d)
{
return (d.b-c.b+c.a-d.a-1)/(c.a-d.a);
}
struct CHT
{
deque<node>d;
void add(const node e)
{
while(d.size()>=2)
{
i64 i1=intersect(d[d.size()-2].a,d.back().a);
i64 i2=intersect(d.back().a,e.a);
if(i1>i2 && (i1==i2 && d.back().k<e.k))
{
d.pop_back();
}
else
{
break;
}
}
d.pb(e);
}
pair<i64,int> query(int val)
{
while(d.size()>=2 && ((d[0].a.calculate(val)>d[1].a.calculate(val)) || (d[0].a.calculate(val)==d[1].a.calculate(val) && d[0].k>=d[1].k)))
{
d.pop_front();
}
return {d[0].a.calculate(val),d[0].k};
}
void clear()
{
d.clear();
}
};
i64 pow2(i64 x)
{
return x*x;
}
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
pair<i64,int> aliens(vector<duo>&a,int n,i64 cost_extra)
{
CHT cht;
cht.add({{-2*(a[0].l-1),pow2(a[0].l-1)},0});
pair<i64,int>sol;
for(int i=0;i<n;i++)
{
sol=cht.query(a[i].r);
sol.first+=pow2(a[i].r)+cost_extra;
sol.second++;
if(i!=n-1)
{
cht.add({{-2*(a[i+1].l-1) , pow2(a[i+1].l-1)-pow2(max(0,a[i].r-a[i+1].l+1))+sol.first},sol.second});
}
}
return sol;
}
i64 take_photos(int n, int m, int k, vector<int> rr, vector<int> cc)
{
vector<duo>a(n);
for(int i=0;i<n;i++)
{
a[i]={min(rr[i],cc[i]),max(rr[i],cc[i])};
}
vector<duo>aux=a;
a.clear();
sort(all(aux));
int maxx=-1;
for(auto &c:aux)
{
if(c.r>maxx)
{
a.pb(c);
maxx=c.r;
}
}
aux.clear();
n=(int)a.size();
k=min(n,k);
i64 st=0,dr=1LL*m*m;
i64 rez=-1;
while(st<=dr)
{
i64 m=(st+dr)/2;
auto sol=aliens(a,n,m);
if(k>=sol.second)
{
dr=m-1;
rez=sol.first-m*sol.second;
}
else
{
st=m+1;
}
}
return rez;
}
