#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = (1ll<<60);
vector<int> vals;
struct Line {
ll a, b;
ll cn;
ll eval(ll x) { if(b == -1)return inf; return (x-a+1)*(x-a+1) + b; }
Line() : a(0), b(-1), cn(0) {}
Line(ll _a, ll _b, ll _cn) : a(_a), b(_b), cn(_cn) {}
};
struct LCT {
int n;
vector<Line> st;
LCT(int sz) : n(sz), st(4*n) {}
void ins(Line f, int l = 0, int r = -2, int p = 1){
if(r == -2)r = n-1;
if(l > r)return;
int m = (l+r)>>1;
bool lb = f.eval(vals[l]) < st[p].eval(vals[l]);
bool mb = f.eval(vals[m]) < st[p].eval(vals[m]);
if(mb)swap(st[p],f);
if(lb == mb)ins(f,m+1,r,p<<1|1);
else ins(f,l,m-1,p<<1);
}
pair<ll,ll> que(ll x, int l = 0, int r = -2, int p = 1){
if(r == -2)r = n-1;
int m = (l+r) >> 1;
if(vals[m] == x)return {st[p].eval(x),st[p].cn};
if(vals[m] < x)return min(make_pair(st[p].eval(x),st[p].cn),que(x,m+1,r,p<<1|1));
return min(make_pair(st[p].eval(x),st[p].cn),que(x,l,m-1,p<<1));
}
};
ll take_photos(int n, int M, int k, vector<int> R, vector<int> C) {
for(int i = 0; i < n; ++i)if(R[i] > C[i])swap(R[i],C[i]);
vector<pair<ll,ll>> v, _v;
for(int i = 0; i < n; ++i)_v.emplace_back(R[i],C[i]);
sort(_v.begin(),_v.end());
v.push_back(_v[0]);
for(int i = 1; i < n; ++i){while(v.size()&& _v[i].first == v.back().first)v.pop_back();if(v.empty() || _v[i].second > v.back().second)v.push_back(_v[i]);}
n = v.size();
if(k >= n){
ll ans = (v[0].second-v[0].first+1)*(v[0].second-v[0].first+1);
for(int i = 1; i < n; ++i){
ans+=(v[i].second-v[i].first+1)*(v[i].second-v[i].first+1);
if(v[i].first <= v[i-1].second)ans-=(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1);
}
return ans;
}
for(int i = 0; i < n; ++i){
vals.push_back(v[i].first);
vals.push_back(v[i].second);
}
sort(vals.begin(),vals.end());
vals.resize( distance(vals.begin(),unique(vals.begin(),vals.end())) );
M = vals.size();
ll l = 0, r = (1ll<<40), ans = 0;
while(l <= r){
ll m = (l+r)>>1;
LCT lct(M);
lct.ins(Line(v[0].first,m,1));
for(int i = 1; i < n; ++i){
pair<ll,ll> cu = lct.que(v[i-1].second);
ll a = v[i].first, b = m+cu.first, cn = cu.second+1;
if(v[i].first <= v[i-1].second){
b-=(v[i-1].second-v[i].first+1)*(v[i-1].second-v[i].first+1);
}
lct.ins(Line(a,b,cn));
}
pair<ll,ll> cu = lct.que(v[n-1].second);
if(cu.second > k){
l = m+1;
}
else{
r = m-1;
ans = cu.first-m*k;
}
}
return ans;
}
