#include "aliens.h"
#include<bits/stdc++.h>
#define fi first
#define se second
using namespace std;
const int MAXN=1e5+5;
const long long INF=1e18;
struct Line
{
long long k,n;
long long st;
int num;
Line() {};
Line(long long _k,long long _n,long long _st,int _num)
{
k=_k;
n=_n;
st=_st;
num=_num;
}
};
int n,m,k;
pair<int,int> tmp[MAXN];
vector<pair<long long,long long> > a;
long long dp[MAXN];
int seg[MAXN];
Line lines[MAXN];
int beg=0, en=-1;
long long crossX(Line a,Line b)
{
long long diffK=a.k-b.k;
long long diffN=b.n-a.n;
if(diffK==0)
{
if(a.n>b.n) return INF;
else return 0;
}
return (diffN+diffK-1)/diffK;
}
void addLine(Line cur)
{
while(en-beg+1>0 && crossX(lines[en], cur)<=lines[en].st) en--;
if(en-beg+1>0) cur.st=crossX(lines[en], cur);
lines[++en]=cur;
}
pair<int,long long> query(long long x)
{
while(en-beg+1>1 && lines[beg+1].st<=x) beg++;
return {lines[beg].num, lines[beg].k*x+lines[beg].n};
}
void resetLines()
{
beg=0;
en=-1;
}
int solve(long long pen)
{
resetLines();
dp[0]=0;
seg[0]=0;
for(int i=1; i<=n; i++)
{
long long x=a[i].fi;
long long t=max(0LL, a[i-1].se-x+1);
addLine(Line(-(x-1)*2, (x-1)*(x-1)-t*t+dp[i-1]+pen, 0, i));
pair<int,long long> qr=query(a[i].se);
dp[i]=qr.se+a[i].se*a[i].se;
seg[i]=seg[qr.fi-1]+1;
}
return seg[n];
}
long long take_photos(int _n, int _m, int _k, std::vector<int> _r, std::vector<int> _c)
{
n=_n; m=_m; k=_k;
for(int i=0; i<n; i++)
{
_r[i]++; _c[i]++;
if(_r[i]>_c[i]) swap(_r[i], _c[i]);
tmp[i+1].fi=_r[i], tmp[i+1].se=_c[i];
}
sort(tmp+1,tmp+n+1,[](pair<long long,long long> x,pair<long long,long long> y)
{
if(x.fi==y.fi) return x.se>y.se;
return x.fi<y.fi;
});
a.push_back({0,0});
for(int i=1; i<=n; i++)
{
if(tmp[i].fi>a.back().fi && tmp[i].se>a.back().se) a.push_back(tmp[i]);
}
n=a.size()-1;
k=min(k,n);
long long l=0,r=1e18;
while(l<r)
{
long long mid=(l+r+1)/2;
if(solve(mid)>=k) l=mid;
else r=mid-1;
}
solve(l);
long long ans=dp[n]-k*l;
return ans;
}
