#include "aliens.h"
#include <iostream>
#include <algorithm>
#include <utility>
const int nmax=100005;
using namespace std;
struct in
{
int l,r;
}v[nmax];
bool operator <(in unu,in doi)
{
if(unu.l==doi.l) return unu.r>doi.r;
return unu.l<doi.l;
}
struct funct
{
long double a,b;
int cate;
void it(long double A,long double B,int c)
{
this->a=A;
this->b=B;
this->cate=c;
}
long double eval(long double x)
{
return a*x+b;
}
}f,st[nmax];
int p,u,i,N;
long double L,R;
pair<long double,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(u>2&&in(f,st[u-1])<in(st[u-1],st[u]))
u--;
st[++u]=f;
}
void gt(long double x)
{
while(p<u&&in(st[p],st[p+1])<x)
p++;
dp[i]={st[p].eval(x),st[p].cate};
dp[i].first+=1LL*x*x;
}
int get(long double C)
{
p=1,u=0;
int pp=0;
long double len;
for(i=1;i<=N;i++)
{
L=v[i].l-1;R=v[i].r;
while(v[pp].r<v[i].l)
pp++;
pp--;
if(pp)len=v[pp].r-v[i].l+1;
else len=0;
if(len<0) len=0;
f.it(-2*L,L*L+dp[pp].first+C-len*len,dp[pp].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);
return dp[N].first;
}
long double ll,rr,mid,kk=k;
ll=0;rr=1LL*1e16;
for(int cnt=1;cnt<=100;cnt++)
{
mid=(ll+rr)/2;
if(get(mid)<=k) rr=mid;
else ll=mid;
}
int ct=get(ll);
long long ans=(long long)(dp[N].first-kk*ll+0.5);
return ans;
}
