#include"aliens.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
const long long INF=2e18;
pair<long long,long long> dp[MAXN],line[MAXN];
double range[MAXN];
long long st[MAXN],ed[MAXN];
int pos[MAXN];
stack<int> ss;
double intersect(pair<long long,long long> a,pair<long long,long long> b)
{
return (double)(b.second-a.second)/(a.first-b.first);
}
void solve(int n,long long cost)
{
int cnt=0;
dp[0]={0,0},range[0]=-INF;
for(int i=1;i<=n;i++)
{
dp[i]={(ed[i]-st[1]+1)*(ed[i]-st[1]+1)+cost,1};
if(!ss.empty())
{
int pp=upper_bound(range,range+cnt+1,ed[i]+1)-range-1;
for(int j=max(0,pp-1),p=pos[j];j<=min(cnt,pp+1);p=pos[++j])
dp[i]=min(dp[i],{(ed[i]+1)*(ed[i]+1+line[p].first)+cost+line[p].second,dp[p].second+1});
}
line[i]={-st[i+1]*2,dp[i].first+st[i+1]*st[i+1]-max(0LL,ed[i]-st[i+1]+1)*max(0LL,ed[i]-st[i+1]+1)};
while(!ss.empty()&&range[cnt]>intersect(line[i],line[ss.top()])) ss.pop(),cnt--;
if(!ss.empty()) range[++cnt]=intersect(line[i],line[ss.top()]),range[cnt+1]=INF;
pos[cnt]=i,ss.push(i);
}
while(!ss.empty()) ss.pop();
}
long long take_photos(int n,int m,int k,vector<int> R,vector<int> C)
{
vector< pair<int,int> > vi;
for(int i=0;i<n;i++) vi.push_back({min(R[i],C[i]),max(R[i],C[i])});
sort(vi.begin(),vi.end());
vector< pair<int,int> > vv;
vv.push_back(vi[0]);
for(int i=1;i<n;i++)
{
if(vv.back().first==vi[i].first) vv.pop_back(),vv.push_back(vi[i]);
else if(vv.back().second<vi[i].second) vv.push_back(vi[i]);
}
n=vv.size(),k=min(k,n);
for(int i=1;i<=n;i++) st[i]=vv[i-1].first,ed[i]=vv[i-1].second;
long long l=0,r=1e13,pos=0;
while(l<=r)
{
long long mid=(l+r)/2;
solve(n,mid);
if(dp[n].second<=k) r=mid-1,pos=mid;
else l=mid+1;
}
solve(n,pos);
return dp[n].first-dp[n].second*pos;
}
