#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;
};
#define db long double
struct ConvexHull_Trick
{
struct Line { i64 a,b; int cnt; } st[100005];
int top,j;
void Init() { top=0; j=1; }
db intersect(Line x,Line y)
{
return (db)(y.b-x.b) / (db)(x.a-y.a);
}
void add(i64 a,i64 b,int cnt)
{
while(top>1)
{
db y1=intersect({ a,b },st[top-1]),y2=intersect(st[top],st[top-1]);
if(y1<y2 || (y1==y2 && st[top].cnt<cnt)) top--;
else break;
}
if(top>0) j=min(j,top);
else j=1;
st[++top]={ a,b,cnt };
}
pair<i64,int> get(i64 x)
{
while(j<top)
{
i64 y1=x*st[j].a+st[j].b,y2=x*st[j+1].a+st[j+1].b;
if(y1>y2 || (y1==y2 && st[j].cnt<st[j+1].cnt)) j++;
else break;
}
return { x*st[j].a+st[j].b,st[j].cnt };
}
}cht;
i64 pow2(i64 x)
{
return x*x;
}
/////////////////////////////////////////////////////
/////////////////////////////////////////////////////
pair<i64,int> aliens(vector<duo>&a,int n,i64 cost_extra)
{
cht.Init();
cht.add(-2*(a[0].l-1),pow2(a[0].l-1),0);
pair<i64,int>sol={-1,-1};
for(int i=0;i<n;i++)
{
sol=cht.get(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;
}
long long 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);
long long st=0,dr=1e12;
long long rez=aliens(a,n,0).first;
while(st<=dr)
{
long long m=(st+dr)/2;
auto sol=aliens(a,n,m);
if(k>=sol.second)
{
dr=m-1;
}
else
{
st=m+1;
rez=sol.first-k*m;
}
}
return rez;
}
