#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+7;
const int M = 1e6;
int a[N];
struct po{
long long x,y;
po(long long fi=0,long long se=0){
x=fi;
y=se;
}
bool operator<(const po& oth)const{
return x<oth.x;
}
po rev(){
return po(y,x);
}
};
long long get(po fi, po se){
return llabs((llabs(se.x-fi.x)+1)*(llabs(se.y-fi.y)+1));
}
long long get_sq( po fi){
return get(fi,fi.rev());
}
long long D(const po& fi,const po& se){
long long d=get(po(fi.x,fi.x),po(se.y,se.y));
d-=get_sq(fi);
d-=get_sq(se);
if(fi.y>=se.x){
d+=get(po(fi.y,fi.y),po(se.x,se.x));
}
return d;
}
multiset<po> pw;
multiset<pair<long long,pair<po,po> > > all;
typedef multiset<po>::iterator mpo;
long long take_photos(int n, int m, int k, std::vector<int> r, std::vector<int> c) {
for(int i=0;i<n;++i){
int x=r[i];
int y=c[i];
if(x>y)swap(x,y);
a[x]=max(a[x],y-x+1);
}
long long cur=0;
for(int i=0;i<=m;++i){
cur--;
if(a[i]>max(0ll,cur)){
pw.insert(po(i,i+a[i]-1));
}
cur=max(cur,1ll*a[i]);
}
multiset<po>::iterator it;
cur=-1;
long long ans=0ll;
for(it=pw.begin();it!=pw.end();++it){
po c=*it;
ans+=get(c,c.rev());
if(cur>=c.x){
ans-=get(po(c.x,c.x),po(cur,cur));
}
cur=max(cur,c.y);
}
po lst=po(-1,-1);
for(it=pw.begin();it!=pw.end();++it){
if(lst.x==-1){
lst=*it;
continue;
}
po c=*it;
long long d=D(lst,c);
all.insert(make_pair(d,make_pair(lst,c)));
lst=c;
}
while(pw.size()>k){
pair< long long, pair< po , po > > q=*all.begin();
it=pw.find(q.second.first);
mpo rg=pw.find(q.second.second);
long long X=it->x;
long long Y=rg->y;
po nor=po(X,Y);
ans+=q.first;
all.erase(all.begin());
mpo e=it;
if(it!=pw.begin()){
e--;
all.erase(all.find(make_pair(D(*e,*it),make_pair(*e,*it))));
all.insert(make_pair(D(*e,nor),make_pair(*e,nor)));
}
mpo nx=rg;
nx++;
if(nx!=pw.end()){
all.erase(all.find(make_pair(D(*rg,*nx),make_pair(*rg,*nx))));
all.insert(make_pair(D(nor,*nx),make_pair(nor,*nx)));
}
pw.erase(rg);
pw.erase(it);
pw.insert(nor);
}
return ans;
}
