#include <bits/stdc++.h>
using namespace std;
#define fr(i,n) for(int i = 0; i<n; i++)
#define sz(v) (int)(v.size())
#define prin(a) cout << #a << " = " << a << endl
#define prinv(v) cout << #v << " = "; for(auto it : v) cout << it << ", "; cout << endl
#define all(v) (v).begin(),(v).end()
typedef long long ll;
#define rmin(a,b) a = min<ll>(a,b)
#define rmax(a,b) a = max<ll>(a,b)
#define fi first
#define se second
struct Line{
// y = m*x + k
ll m,k,qnt;
ll eval(ll x){
return m*x+k;
}
Line(){}
Line(ll _m, ll _k, ll _qnt){
m = _m, k = _k, qnt = _qnt;
}
};
//querys em ordem de x decrescente
//insercoes de linhas com m (slopes) em ordem decrescente
struct ChtDeque{
vector<Line> dq;
int l, r; // [l,r)
ChtDeque(){}
ChtDeque(int n){ //n eh o maximo de linhas a serem inseridas
n+=5;
dq.resize(n+5);
l = r = 3;
}
ll div(ll a, ll b){
return a/b - ( (a^b)<0 and a%b);
}
bool tirar(Line &l1, Line &l2, Line &l3){
if(l1.m==l2.m){
return l1.k>=l2.k;
}
return div(l2.k-l3.k,l3.m-l2.m)<=div(l1.k-l2.k,l2.m-l1.m);
}
void add(ll m, ll k, ll qnt){
m*=-1,k*=-1;
Line line(m,k,qnt);
/*
while(r-l>=2){
if(tirar(dq[r-2],dq[r-1],line)) r--;
else break;
}
if(l<r and dq[l].m==m){
if(k>dq[l].k or (k==dq[l].k and qnt<dq[l].qnt)) dq[l] = line;
return;
}
*/
dq[r++] = line;
}
pair<ll,ll> query(ll x){
assert(r>l);
///*
ll maxv = -LLONG_MAX, minqnt = 0;
for(int i = l; i<r; i++){
ll cur = dq[i].eval(x);
ll curq = dq[i].qnt;
if(cur>maxv or (cur==maxv and curq<minqnt)){
maxv = cur;
minqnt = curq;
}
}
return {-maxv,minqnt};
//*/
while(r-l>=2){
ll val_l = dq[l].eval(x);
ll val_l1 = dq[l+1].eval(x);
if(val_l1>=val_l) l++;
else break;
}
return {-dq[l].eval(x),dq[l].qnt};
}
};
vector<pair<ll,ll>> vp;
int debug = 0;
//ans min, k used
pair<ll,ll> f(ll c){
ChtDeque cht(sz(vp)+1);
ll udp = 0, uqnt = 0;
fr(i,sz(vp)){
ll ri,ci; tie(ri,ci) = vp[i];
ci++;
ll sub = 0;
if(i){
ll rj,cj; tie(rj,cj) = vp[i-1];
cj++;
if(cj>ri) sub = (cj-ri)*(cj-ri);
}
cht.add(-2*ri,ri*ri+udp+c-sub,uqnt);
ll dp, qnt; tie(dp,qnt) = cht.query(ci);
dp+=ci*ci;
qnt++;
udp = dp, uqnt = qnt;
}
return {udp,uqnt};
}
ll take_photos(int n, int m, int k, vector<int> vr, vector<int> vc){
vp.clear();
fr(i,n){
if(vc[i]<vr[i]) swap(vc[i],vr[i]);
vp.emplace_back(vr[i],vc[i]);
}
{
sort(all(vp));
reverse(all(vp));
vector<pair<ll,ll>> aux;
for(auto &[i,j] : vp){
if(!aux.empty() and aux.back().fi==i) continue;
while(!aux.empty() and j>=aux.back().se) aux.pop_back();
aux.emplace_back(i,j);
}
reverse(all(aux));
vp = aux;
}
/*
for(auto &[i,j] : vp){
prin(i);
prin(j);
cout << endl;
}
//*/
ll lo = 0, hi = m*m;
while(lo<hi){
ll mid = (lo+hi)/2;
if(f(mid).se<=k) hi = mid;
else lo = mid+1;
};
auto par = f(lo);
/*
prin(lo);
prin(par.fi);
prin(k);
prin(par.se);
*/
return par.fi-par.se*lo;
/*
lo = 30;
prin(lo);
auto par = f(lo);
prin(par.fi);
prin(k);
prin(par.se);
return par.fi-par.se*lo;
*/
}
