#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll inf = (1ll<<50);
const int mxN = 1e5+5;
struct line{
ll a, b;
int cn;
line(ll _a, ll _b, int _cn) : a(_a), b(_b), cn(_cn) {}
line(ll _a, ll _b) : line(_a, _b, 0) {}
ll eval(ll x){if(b == (1ll<<60))return (1ll<<60); return (x-a+1)*(x-a+1)+b;}
};
vector<int> vals;
struct LCT{
vector<line> st;
LCT(int n) : st(4*n,line(0,1ll<<60)) {}
void ins(line f, int l, int r, int p){
if(l > r)return;
int m = (l+r)>>1;
bool lf = st[p].eval(vals[l]) > f.eval(vals[l]);
bool mf = st[p].eval(vals[m]) > f.eval(vals[m]);
if(mf)swap(st[p],f);
if(lf == mf)ins(f,m+1,r,p<<1|1);
else ins(f,l,m-1,p<<1);
}
line que(int x, int l, int r, int p){
int m = (l+r)>>1;
if(vals[m] == x)return st[p];
if(vals[m] > x){
line cu = que(x,l,m-1,p<<1);
return cu;
}
else{
line cu = que(x,m+1,r,p<<1|1);
return cu;
}
}
};
bool cmp(pair<int,int> &a, pair<int,int> &b){
if(a.first == b.first)return a.second > b.second;
return a.first < b.first;
}
ll take_photos(int N, int M, int k, vector<int> R, vector<int> C) {
vector<pair<int,int>> _v, v;
for(int i = 0; i < N; ++i){if(R[i] > C[i])swap(R[i],C[i]);_v.push_back({R[i],C[i]});}
sort(_v.begin(),_v.end(),cmp);
v.push_back(_v[0]);
for(int i = 1; i < N; ++i){if(_v[i].second <= v.back().second)continue;v.push_back(_v[i]);}
for(auto &x : v)swap(x.first,x.second);
N = v.size();
for(int i = 0; i < N; ++i)vals.push_back(v[i].first);
// dp[n][n][k] current index : start : amount
// remove k with alien trick
// remove second n with CHT (LiChaoTree)
// O(n log^2(n))
ll l = 0, r = inf, ans = 0;
while(l <= r){
ll m = (l+r)>>1;
LCT lct(N);
lct.ins(line(v[0].second,m,1),0,N-1,1);
for(int i = 1; i < N; ++i){
line cu = lct.que(v[i-1].first,0,N-1,1);
ll a = v[i].second, b = m + cu.eval(v[i-1].first), cn = cu.cn+1;
if(v[i-1].first >= v[i].second){
b-=(v[i-1].first-v[i].second+1)*(v[i-1].first-v[i].second+1);
}
lct.ins(line(a,b,cn),0,N-1,1);
}
line cu = lct.que(v[N-1].first,0,N-1,1);
if(cu.cn > k){
l = m+1;
}
else{
r = m-1;
ans = cu.eval(v[N-1].first)-m*k;
}
}
return ans;
}
