#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
using lint=int64_t;
using pii=pair<lint,lint>;
#define pb push_back
struct cht{
struct state{
lint first,second,aux;
};
deque<state>st;
void insert(lint a,lint b,lint aux){
int sz;
while(
1<(sz=st.size())
&&
(st[1].second-b)*(st[0].first-st[1].first)
<
(a-st[1].first)*(st[1].second-st[0].second)
){
st.pop_front();
}
st.push_front({a,b,aux});
}
pii query(lint x){
int sz;
while(
1<(sz=st.size())
&&
st[sz-2].first*x+st[sz-2].second
<
st[sz-1].first*x+st[sz-1].second
){
st.pop_back();
}
sz=st.size();
lint res=st[sz-1].first*x+st[sz-1].second;
return pii{res,st[sz-1].aux};
}
};
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c) {
for(int i=0;i<n;i++){
if(c[i]<R[i]){
swap(c[i],R[i]);
}
}
int points[m+1];
memset(points,-1,sizeof(points));
for(int i=0;i<n;i++){
points[R[i]]=max(points[R[i]],c[i]);
}
vector<pii>pts;
for(int i=0;i<=m;i++){
if(points[i]!=-1){
if(!pts.size()||pts.back().second<points[i]){
pts.pb(pii{i,points[i]});
}
}
}
n=pts.size();
lint ans=LLONG_MAX;
lint dp[n+1],aux[n+1],b[n+1];
b[0]=(pts[0].first-2)*pts[0].first;
for(int i=1;i<=n;i++){
if(i==n)b[i]=0;
else{
b[i]=-(pts[i].first<=pts[i-1].second?
(pts[i-1].second-pts[i].first+1)*(pts[i-1].second-pts[i].first+1)
:0)+(pts[i].first-2)*pts[i].first;
}
}
cht st;
lint l=0,r=1000000000100;
while(l<=r){
lint lambda=(l+r)>>1;
st.st.clear();
dp[0]=0;
aux[0]=0;
st.insert(-2*pts[0].first,b[0],0);
for(int i=1;i<=n;i++){
lint y=pts[i-1].second;
pii res=st.query(y);
dp[i]=res.first+y*y+2*y+1+lambda;
aux[i]=res.second+1;
if(i<n)st.insert(-2*pts[i].first,b[i]+dp[i],aux[i]);
}
if(aux[n]<=k){
ans=min(ans,dp[n]-lambda*aux[n]);
r=lambda-1;
}else{
l=lambda+1;
}
}
return ans;
}
