#include "aliens.h"
#include <bits/stdc++.h>
#define N 100005
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
int n,m;
stack<P> sstk;
P aa[N],a[N];
ll dp[N],use[N][2],d[N],l;
ll res[N];
ll cmax;int lv,rv;
struct line
{
ll a,b;
int mn,mx;
line(ll aa,ll bb){
a=aa;
b=bb;
mn=mx=0;
}
line(ll aa,ll bb,int m1,int m2){
a=aa;
b=bb;
mn=m1;
mx=m2;
}
line(){a=b=mn=mx=0;}
ll get(ll x){return a*x+b;}
};
struct node
{
line a;
node *l=nullptr,*r=nullptr;
node(ll aa,ll bb){
a.a=aa;
a.b=bb;
}
node(line x){
a=x;
}
ll get(ll x){return a.get(x);}
};
struct lichao
{
node *root=nullptr;
ll query(ll x){return query(root,1,1e6,x);}
ll query(node *nd,ll l,ll r,ll x){
if(nd==nullptr) return 1e15;
ll res=nd->get(x);
if(cmax>res){
lv=nd->a.mn;
rv=nd->a.mx;
cmax=res;
}
else if(cmax==res){
lv=min(lv,nd->a.mn);
rv=max(rv,nd->a.mx);
}
if(l==r) return res;
ll m=(l+r)/2;
if(x<=m&&nd->l!=nullptr)
return min(res,query(nd->l,l,m,x));
if(x>m&&nd->r!=nullptr)
return min(res,query(nd->r,m+1,r,x));
return res;
}
void update(ll a,ll b,int mn,int mx){line ln=line(a,b,mn,mx);update(root,1,1e6,ln);}
typedef node* pnd;
void update(pnd &nd,ll l,ll r,line &a){
if(nd==nullptr){
nd=new node(a);
return;
}
if(nd->get(l)<a.get(l)&&nd->get(r)<a.get(r)) return;
if(nd->get(l)>a.get(l)&&nd->get(r)>a.get(r)){
nd->a=a;
return;
}
ll m=(l+r)/2;
if(nd->get(m)>a.get(m))
swap(nd->a,a);
if(nd->get(l)<a.get(l))
update(nd->r,m+1,r,a);
else
update(nd->l,l,m,a);
}
};
void solve(ll lambda)
{
for(int i=0;i<n;i++)
dp[i]=use[i][0]=use[i][1]=0;
lichao lc;
for(int i=0;i<n;i++){
dp[i]=(a[0].x-a[i].y-1)*(a[0].x-a[i].y-1)+lambda;
lv=rv=0;
cmax=dp[i]-a[i].y*a[i].y-2*a[i].y-1-lambda;
if(i>0){
ll newv=lc.query(a[i].y)+a[i].y*a[i].y+2*a[i].y+1+lambda;
if(newv<dp[i])
dp[i]=newv;
}
lv++;rv++;
use[i][0]=lv;
use[i][1]=rv;
lc.update(-2LL*a[i+1].x,dp[i]+d[i]+a[i+1].x*a[i+1].x-2LL*a[i+1].x,lv,rv);
}
}
ll take_photos(int n_,int m_,int k_,vector<int> r,vector<int> c)
{
n=n_;m=m_;l=k_;
for(int i=0;i<n;i++)
aa[i]=P(min(r[i],c[i]),max(r[i],c[i]));
sort(aa,aa+n);
for(int i=0;i<n;i++){
while(sstk.size()&&sstk.top().x==aa[i].x)
sstk.pop();
if(sstk.size()&&sstk.top().y<=aa[i].y)
sstk.push(aa[i]);
else if(!sstk.size())
sstk.push(aa[i]);
}
n=0;
while(sstk.size()){
a[n++]=sstk.top();
sstk.pop();
}
sort(a,a+n);
for(int i=0;i<n;i++){
if(i<n-1&&a[i].y>=a[i+1].x)
d[i]=-(ll)(a[i].y-a[i+1].x+1)*(ll)(a[i].y-a[i+1].x+1);
}
ll L=-(ll)m*m*1000,R=-L,ans=1e18;
while(L<=R){
ll M=(L+R)/2;
solve(M);
if(use[n-1][1]>=l&&use[n-1][0]<=l)
return dp[n-1]-M*l;
if(use[n-1][1]<=l){
R=M-1;
ans=min(ans,dp[n-1]-M*use[n-1][1]);
}
else
L=M+1;
}
return ans;
}
