#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
struct line
{
long long res, cf, tm;
long long brp;
line() {}
line(long long a, long long b, long long c, long long d)
{
res=a;
cf=b;
tm=c;
brp=d;
}
};
long long N;
pair<long long, long long> pr[100005];
long long id=0;
long long T, ans, totbr;
vector<line> lines;
void add_line(long long k)
{
long long res, br, tm, cf;
while(id!=lines.size()-1 && lines[id+1].tm<=pr[k].second) id++;
res=lines[id].res+(pr[k].second-lines[id].cf+1)*(pr[k].second-lines[id].cf+1)+T;
br=lines[id].brp+1;
if(k==N-1)
{
ans=res;
totbr=br;
}
else
{
cf=pr[k+1].first;
if(cf<=pr[k].second) res-=(pr[k].second-cf+1)*(pr[k].second-cf+1);
long long tN=lines.size();
while(tN>id)
{
long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf;
if((vr-cf+1)*(vr-cf+1)+res<=(vr-cf2+1)*(vr-cf2+1)+res2) tN--;
else break;
}
lines.resize(tN);
if(tN==id) lines.push_back(line(res, cf, -1, br));
else
{
long long vr=lines[tN-1].tm, res2=lines[tN-1].res, cf2=lines[tN-1].cf, tm;
tm=(res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)/(2*cf-2*cf2);
if((res+(cf-1)*(cf-1)-(cf2-1)*(cf2-1)-res2)%(2*cf-2*cf2)) tm++;
lines.push_back(line(res, cf, tm, br));
}
}
}
pair<long long, long long> solve()
{
id=0;
lines.resize(0);
lines.push_back(line(0, pr[0].first, -1, 0));
for(long long i=0; i<N; i++) add_line(i); ///cout<<lines[lines.size()-1].res<<' '<<lines[lines.size()-1].cf<<" "<<lines[lines.size()-1].brp<<endl;}
return {totbr, ans};
}
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c)
{
N=n;
for(int i=0; i<n; i++) if(r[i]>c[i]) swap(r[i], c[i]);
for(int i=0; i<n; i++) pr[i]={r[i], c[i]};
sort(pr, pr+N);
long long id=0;
for(long long i=1; i<N; i++)
{
if(pr[i].second<=pr[id].second) continue;
if(pr[i].first!=pr[id].first) id++;
swap(pr[id], pr[i]);
}
N=n=id+1;
k=min(k, n);
///for(long long i=0; i<n; i++) cout<<pr[i].first<<" "<<pr[i].second<<endl;
long long le=0, ri=1e12;
while(ri-le>1)
{
long long mid=(le+ri)/2;
T=mid;
pair<long long, long long> pr=solve();
///cout<<T<<" "<<pr.second<<" "<<pr.first<<endl;
if(pr.first==k) return pr.second-mid*k;
else if(pr.first<k) ri=mid;
else le=mid;
}
T=le;
pair<long long, long long> pr=solve();
return pr.second-T*k;
}
