#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
const int nmax=100005;
using namespace std;
struct in
{
int l,r;
}v[nmax];
typedef long long ld;
bool operator <(in unu,in doi)
{
if(unu.l==doi.l) return unu.r>doi.r;
return unu.l<doi.l;
}
struct funct
{
ld a,b;
int cate;
void it(ld A,ld B,int c)
{
this->a=A;
this->b=B;
this->cate=c;
}
ld eval(ld x)
{
return a*x+b;
}
}f,st[nmax];
int p,u,i,N;
ld L,R;
pair<ld,int> dp[nmax];
long double a1,a2,b1,b2;
long double in(funct unu,funct doi)
{
a1=unu.a;a2=doi.a;b1=unu.b;b2=doi.b;
return (b2-b1)/(a1-a2);
}
void ins()
{
while(p<u&&in(f,st[u-1])<in(st[u-1],st[u]))
u--;
st[++u]=f;
}
void gt(ld x)
{
while(p<u&&in(st[p],st[p+1])<(long double)x)
p++;
dp[i]={st[p].eval(x),st[p].cate};
dp[i].first+=1LL*x*x;
}
int get(ld C)
{
p=1,u=0;
long double len=0;
for(i=1;i<=N;i++)
{
L=v[i].l-1;R=v[i].r;
if(i>1)len=v[i-1].r-v[i].l+1;
else len=0;
if(len<0) len=0;
f.it(-2*L,L*L+dp[i-1].first+C-len*len,dp[i-1].second+1);
ins();
gt(R);
}
return dp[N].second;
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(i=0;i<n;i++)
{
r[i]++,c[i]++;
v[i+1].l=min(r[i],c[i]);
v[i+1].r=max(r[i],c[i]);
}
sort(v+1,v+n+1);
int mx=0,nr=0;
for(i=1;i<=n;i++)
{
if(mx<v[i].r)
{
v[++nr]=v[i];
}
mx=max(mx,v[i].r);
}
N=n=nr;
if(N<=k)
{
int ct=get(0);
long long ans=dp[N].first;
return ans;
}
ld ll,rr,mid,kk=k;
ll=(1LL<<40);
for(int p=39;p>=0;p--)
if(get(ll-(1LL<<p))<=k)
ll-=(1LL<<p);
int ct=get(ll);
long long ans=(long long)(dp[N].first-kk*ll);
return ans;
}
