#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
vector<pii>Vtmp,V;
lint sq(int L)
{
return 1ll*L*L;
}
int a[100004],b[100004];
struct Line{
lint a,b;
int k;
};
int piv,knum;
vector<Line>CHT;
lint D;
bool check1(Line A,Line B,Line C)
{
if((long double)(B.b-A.b)/(A.a-B.a) > (long double)(C.b-B.b)/(B.a-C.a))return 1;
else return 0;
}
bool check2(Line A,Line B,lint x)
{
if((B.b-A.b) < x*(A.a-B.a)) return 1;
else return 0;
}
void insert_line(Line L)
{
while((int)CHT.size()>1 && check1(CHT[sz(CHT)-2],CHT[sz(CHT)-1],L))CHT.pop_back();
CHT.push_back(L);
piv=min(piv,sz(CHT)-1);
}
lint gets(lint x)
{
while(piv+1<sz(CHT) && check2(CHT[piv],CHT[piv+1],x))piv++;
knum=CHT[piv].k+1;
return CHT[piv].a * x + CHT[piv].b;
}
lint take_photos(int n, int m, int K, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;i++)
{
if(r[i]<c[i])swap(r[i],c[i]);
Vtmp.push_back({r[i],-c[i]});
}
sort(Vtmp.begin(),Vtmp.end());
int mini=1e9;
for(int i=sz(Vtmp)-1;i>=0;i--)
{
if(mini>-Vtmp[i].second)V.push_back({Vtmp[i].first,-Vtmp[i].second});
mini=min(mini,-Vtmp[i].second);
}
sort(V.begin(),V.end());
n=sz(V);
for(int i=1;i<=n;i++)
{
a[i]=V[i-1].second;
b[i]=V[i-1].first+1;
}
K=min(K,n);
lint p=0,q=1ll*m*m,h;
while(p!=q-1)
{
h=(p+q)/2;
CHT.clear();
insert_line({-4*a[1],2*sq(a[1]),0});
piv=0;
for(int i=1;i<=n;i++)
{
D=gets(b[i])+2*sq(b[i])+(2*h+1);
insert_line({-4*a[i+1],D+2*(sq(a[i+1])-sq(b[i]-min(a[i+1],b[i]))),knum});
}
if(knum==K)return (D-(2*h+1)*knum)/2;
else if(knum>K)p=h;
else q=h;
}
CHT.clear();
insert_line({-4*a[1],2*sq(a[1]),0});
piv=0;
for(int i=1;i<=n;i++)
{
D=gets(b[i])+2*sq(b[i])+(2*p+1);
insert_line({-4*a[i+1],D+2*(sq(a[i+1])-sq(b[i]-min(a[i+1],b[i]))),knum});
}
return (D-(2*p+1)*knum)/2+(p+1)*(knum-K);
}
