#include "aliens.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define sz(x) ((int)x.size())
using namespace std;
#ifdef LOCAL
#define debug(...) _dbg(#__VA_ARGS__, __VA_ARGS__)
#else
#define debug(...) (__VA_ARGS__)
#define cerr if(0)cout
#endif
template<class TH> void _dbg(const char *sdbg, TH h){cerr<<sdbg<<"="<<h<<"\n";}
template<class TH, class... TA> void _dbg(const char *sdbg, TH h, TA...a){
while(*sdbg!=',')cerr<<*sdbg++;cerr<<"="<<h<<","; _dbg(sdbg+1, a...);
}
typedef long long ll;
struct point {
ll r,c;
bool operator<(const point& b)const {
return r==b.r?c>b.c:r<b.r;
}
};
struct CHT {
struct line {
ll a,b,c;
};
vector<line> ln;
int cur;
void clear(){cur=0;ln.clear();}
bool bad(line& a,line& b,line& c) {
return (a.b-b.b)*(c.a-b.a)>(b.b-c.b)*(b.a-a.a);
}
bool bad2(line& a,line& b,ll x) {
return (b.b-a.b)<x*(a.a-b.a);
}
void insert(ll a,ll b,ll c) {
line t={a,b,c};
while(sz(ln)>=2&&bad(ln[sz(ln)-2],ln.back(),t))ln.pop_back();
ln.push_back(t);
}
pair<ll,ll> query(ll x) {
cur=min(cur,sz(ln)-1);
while(cur+1<sz(ln)&&bad2(ln[cur],ln[cur+1],x))cur++;
return {x*ln[cur].a+ln[cur].b,ln[cur].c};
}
}cht;
vector<point> v,tmp;
int n,m,k;
pair<ll,ll> f(ll x) {
int i;
pair<ll,ll> cur,pre;
cht.clear();
for(i=0;i<n;i++) {
ll a=-2*(v[i].r-1);
ll b=(v[i].r-1)*(v[i].r-1)+pre.fi;
ll c=pre.se;
if(i&&v[i-1].c>=v[i].r) {
b-=(v[i-1].c-v[i].r+1)*(v[i-1].c-v[i].r+1);
}
//dp[i]=min((c[i]-r[j]+1)*(c[i]-r[j]+1)+dp[j-1])+x;
cht.insert(a,b,c);
pair<ll,ll> r=cht.query(v[i].c);
cur={r.fi+v[i].c*v[i].c+x,r.se+1};
pre=cur;
}
debug(cur.se);
return cur;
}
long long take_photos(int n_, int m_, int k_, std::vector<int> r_, std::vector<int> c_) {
v.clear();tmp.clear();
n=n_,m=m_,k=k_;
int i,j;
for(i=0;i<n;i++) {
if(r_[i]>c_[i])swap(r_[i],c_[i]);
tmp.push_back({r_[i],c_[i]});
}
sort(tmp.begin(),tmp.end());
for(i=0,j=-1;i<n;i++) {
if(tmp[i].c>j) {
j=tmp[i].c;
v.push_back(tmp[i]);
}
}
n=sz(v);
ll lo=0,hi=1e13;
while(lo<hi) {
ll mid=(lo+hi)/2;
if(f(mid).se>k)lo=mid+1;
else hi=mid;
}
pair<ll,ll> ans=f(lo);
return ans.fi-lo*k;
}
