#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pf printf
#define pb push_back
#define ppb pop_back
#define ppf pop_front
#define INF 1023456789
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
typedef long long ll;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef pair<pair<ll,ll>,int> line;
#define maxn 100005
int n,cnt[maxn];
ll dp[maxn];
deque<line> dq;
vector<ii> pts,tmp;
inline ll sq(ll x){
return x*x;
}
inline ld poi(line a,line b){
auto[m1,c1]=a.fi;
auto[m2,c2]=b.fi;
return (ld)(c1-c2)/(m2-m1);
}
inline ll eval(line a,ll x){
return a.fi.fi*x+a.fi.se;
}
int calc(ll cost){
while(!dq.empty())dq.ppb();
for(int i=1;i<n;++i){
ll m=-2*(pts[i].fi-1);//always distinct
ll c=dp[i-1]+cost+sq(pts[i].fi-1)-sq(max(0,pts[i-1].se-pts[i].fi+1));
line l={{m,c},i-1};
while(sz(dq)>=2&&poi(dq[sz(dq)-1],l)<=poi(dq[sz(dq)-1],dq[sz(dq)-2]))dq.ppb();
dq.pb(l);
while(sz(dq)>=2&&eval(dq[0],pts[i].se)>eval(dq[1],pts[i].se))dq.ppf();
dp[i]=eval(dq[0],pts[i].se)+sq(pts[i].se);
cnt[i]=cnt[dq[0].se]+1;
}
return cnt[n-1];
}
ll take_photos(int _n,int m,int k,vi r,vi c){
n=_n;
for(int i=0;i<n;++i){
if(r[i]>c[i])swap(r[i],c[i]);
tmp.pb({r[i],c[i]});
}
sort(all(tmp),[](ii &a,ii&b){
if(a.fi==b.fi)return a.se>b.se;
else return a.fi<b.fi;
});
pts.pb({-1,-1});
for(int i=0;i<n;++i){
if(pts.back().se<tmp[i].se)pts.pb(tmp[i]);
}
n=pts.size();
ll lo=0,hi=1e12,mid,res=1e12;
while(lo<=hi){
mid=(lo+hi)>>1;
if(calc(mid)<=k)res=mid,hi=mid-1;
else lo=mid+1;
}
calc(res);
return dp[n-1]-res*k;
}
