#include "aliens.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define pb push_back
#define sz(x) ((ll)(x).size())
#define all(x) (x).begin(),(x).end()
const ll M = 1e6 + 5;
struct Line{
ll mx,b,ind;
ll get(ll x){return mx*x+b;}
}seg[4*M];
vector<array<ll,2>> v;
vector<ll> intr;
Line query(int rt,int l,int r,ll u){
if(l==r) return seg[rt];
int m=(l+r)/2;
if(u<=m){
if(seg[rt*2].ind==-1) return seg[rt];
Line left = query(rt*2,l,m,u);
if(left.get(u)<seg[rt].get(u)) return left;
else return seg[rt];
}
else{
if(seg[rt*2+1].ind==-1) return seg[rt];
Line right = query(rt*2+1,m+1,r,u);
if(right.get(u)<seg[rt].get(u)) return right;
else return seg[rt];
}
}
void upd(int rt,int l,int r,Line cur){
if(seg[rt].ind==-1){
seg[rt]=cur;
return;
}
int m=(l+r)/2;
if(cur.get(m)<seg[rt].get(m)) swap(seg[rt],cur);
if(l==r) return;
if(seg[rt].mx<=cur.mx) upd(rt*2,l,m,cur);
else upd(rt*2+1,m+1,r,cur);
}
array<ll,2> f(ll lambda){
int N = sz(v);
ll dp[N+5],cnt[N+5];
cnt[0]=dp[0]=0;
for(int i=0;i<4*M;i++) seg[i].mx=seg[i].b=seg[i].ind=-1;
for(int i=1;i<=N;i++){
Line xd; xd.ind=i-1;
xd.mx = -2 * v[i-1][0] ; xd.b = dp[i-1] - intr[i-1] + v[i-1][0]*v[i-1][0] - 2*v[i-1][0];
upd(1,1,M,xd);
ll xx = v[i-1][1];
Line qq = query(1,1,M,xx);
dp[i] = (xx+1)*(xx+1) + lambda + qq.get(xx);
cnt[i]=cnt[qq.ind]+1;
}
return {dp[N],cnt[N]};
}
ll take_photos(int n,int m,int k, vector<int> r, vector<int> c){
for(int i=0;i<n;i++){
r[i]++;
c[i]++;
}
for(int i=0;i<n;i++) if(r[i]>c[i]) swap(r[i],c[i]);
for(int i=0;i<n;i++) v.pb({r[i],c[i]});
sort(all(v));
vector<array<ll,2>> cur;
for(int i=0;i<n;i++){
while(!cur.empty() && cur.back()[0]==v[i][0]) cur.pop_back();
if(cur.empty() || v[i][1]>cur.back()[1]) cur.pb(v[i]);
}
swap(v,cur);
intr.resize(sz(v)+5);
intr[0]=0;
for(int i=1;i<sz(v);i++) intr[i]=max(v[i-1][1]-v[i][0]+1,0LL)*max(v[i-1][1]-v[i][0]+1,0LL);
ll bl=0,br=m*m;
while(bl<br){
ll mid=(bl+br)/2;
if(f(mid)[1]>k) bl=mid+1;
else br=mid;
}
return f(bl)[0]-k*bl;
}
