#include "aliens.h"
#include <bits/stdc++.h>
#define int long long
#define ld long double
#define fi first
#define se second
using namespace std;
const int INF=1e18;
int n,dp[100001],s[100001],e[100001],mn[100001],mx[1000001],pos[100001],cnt[100001];
vector <pair <int, int>> v,ve;
int ce(int a, int b){
return a/b-(((a<0&&b>0)||(a>0&&b<0))&&a/b*b!=a);
}
ld intersection(pair <int, int> p, pair <int, int> p2){
if (p.fi==p2.fi)
return (p2.se>p.se?INF:-INF);
return ((ld)(p2.se-p.se))/(p.fi-p2.fi);
}
void add(pair <int, int> p, int i){
while (v.size()>1){
ld p12=intersection(v[v.size()-2],v.back()),p13=intersection(v[v.size()-2],p);
if (p12>p13)
break;
v.pop_back();
if (!ve.empty())
ve.pop_back();
}
if (!v.empty()&&(v.back().fi==p.fi))
return;
if (!v.empty())
ve.push_back({ce(p.se-v.back().se,v.back().fi-p.fi),v.size()});
pos[v.size()]=i;
v.push_back(p);
}
pair <int, int> get(int x){
int l=0,r=((int)ve.size())-1,kq=0;
while (l<=r){
int mid=(l+r)>>1;
if (ve[mid].fi>=x){
kq=ve[mid].se;
l=mid+1;
}
else
r=mid-1;
}
return {v[kq].fi*x+v[kq].se,pos[kq]};
}
pair <int, int> check(int x){
v.clear();
ve.clear();
for (int i=n-1;i>=0;i--){
add({-2*(e[i]+1),dp[i+1]+mn[i]*(e[i]*2-mn[i]+2)+x},i);
auto [v,j]=get(s[i]);
dp[i]=v+s[i]*s[i];
cnt[i]=cnt[j+1]+1;
}
return {dp[0],cnt[0]};
}
long long take_photos(int32_t N, int32_t M, int32_t K, vector <int32_t> R, vector <int32_t> C){
memset(mx,-1,sizeof(mx));
for (int i=0;i<N;i++)
mx[min(R[i],C[i])]=max(mx[min(R[i],C[i])],(int)max(R[i],C[i]));
for (int i=0;i<M;i++)
if (mx[i]!=-1)
ve.emplace_back(i,mx[i]);
sort(ve.begin(),ve.end());
int cur=-1;
for (auto [i,j]:ve)
if (j>cur){
s[n]=i;
e[n]=j;
n++;
cur=j;
}
s[n]=INF;
K=min(K,(int32_t)n);
for (int i=0;i<n;i++)
mn[i]=min(s[i+1],e[i]+1);
int l=0,r=1e12,kq=-1;
while (l<=r){
int mid=(l+r)/2;
auto [mx,c]=check(mid);
if (c>=K){
kq=mx-K*mid;
l=mid+1;
}
else
r=mid-1;
}
return kq;
}
