#include <bits/stdc++.h>
#include "aliens.h"
using namespace std;
#define mp make_pair
#define fr first
#define sc second
const long long ub=1e12;
long long nn=0,sl[100069],wg[100069],sk[100069];
pair<long long,long long> a[100069],dp[100069];
long long f(long long x,long long w)
{
return sl[x]*w+wg[x];
}
bool cmp(long long x,long long y,long long x2,long long y2)
{
return mp(x/y,x%y*y2)>mp(x2/y2,x2%y2*y);
}
bool chk(long long x,long long y,long long y2)
{
return cmp(wg[x]-wg[y2],sl[y2]-sl[x],wg[x]-wg[y],sl[y]-sl[x]);
}
long long take_photos(int n,int m,int d,vector<int> ya,vector<int> xa)
{
long long i,k,x,y,y2,sz,p,sm,c,lh,rh,md,zz,zm;
for(i=1;i<=n;i++)
{
y=ya[i-1]+1;
x=xa[i-1]+1;
if(x<y)
{
swap(x,y);
}
y--;
a[i]={x,-y};
}
sort(a+1,a+n+1);
sz=n;
n=0;
for(i=1;i<=sz;i++)
{
x=a[i].fr;
y=-a[i].sc;
for(;n&&a[n].sc>=y;n--);
n++;
a[n]={x,y};
}
a[n+1].sc=m+1;
for(lh=0,rh=ub;lh<=rh;)
{
md=(lh+rh)/2;
nn=0;
p=0;
for(i=0;i<=n;i++)
{
x=a[i].fr;
y=a[i].sc;
y2=a[i+1].sc;
if(i)
{
for(;p<nn&&(!p||f(sk[p+1],x)<f(sk[p],x));p++);
dp[i]={f(sk[p],x)+x*x+md,dp[sk[p]].sc+1};
}
sl[i]=-y2*2;
k=max(x-y2,0ll);
wg[i]=dp[i].fr-k*k+y2*y2;
for(;nn>=2&&chk(i,sk[nn],sk[nn-1]);nn--);
p=min(p,nn);
nn++;
sk[nn]=i;
}
sm=dp[n].fr;
c=dp[n].sc;
if(c<=d)
{
zz=md;
zm=sm;
rh=md-1;
}
else
{
lh=md+1;
}
}
return zm-zz*d;
}
