#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
const int MAXN = 1e5 + 5;
vector<pll> vc, vc2;
deque<pair<pll, int>>hull;
deque<ll> kes;
ll g[MAXN];
ll kc[MAXN];
ll eval(pll ln, ll idx){
return ln.ff*idx + ln.ss;
}
ll iter(pll a, pll b){
ll df1 = b.ss - a.ss;
ll df2 = a.ff - b.ff;
ll idx = df1 / df2 + ((df1 % df2) != 0)*((df1 < 0) ^ (df2 < 0)) * (-1);
return idx;
}
pll gt(ll idx){
while(!kes.empty() && kes[0] < idx){
kes.pop_front();
hull.pop_front();
}
return {eval(hull[0].ff, idx), hull[0].ss};
}
void add(ll a, ll b, int idx){
if(hull.empty()){
hull.push_back({{a, b}, idx});
return;
}
while(!kes.empty() && eval({a, b}, kes.back()) <= eval(hull.back().ff, kes.back())){
kes.pop_back();
hull.pop_back();
}
kes.push_back(iter({a, b}, hull.back().ff));
hull.push_back({{a, b}, idx});
}
pll check(ll C){
int n = vc.size();
hull.clear();
kes.clear();
g[0] = 0;
kc[0] = 0;
add(-2*(vc[0].ff - 1), (vc[0].ff - 1)*(vc[0].ff - 1), 0);
for(int i = 1; i <= n; i++){
pll u = gt(vc[i - 1].ss);
g[i] = vc[i - 1].ss*vc[i - 1].ss + C + u.ff;
kc[i] = kc[u.ss] + 1;
if(i != n)
add(-2*(vc[i].ff - 1), (vc[i].ff - 1)*(vc[i].ff - 1) - (ll)pow(max(vc[i - 1].ss - vc[i].ff + 1, 0LL), 2) + g[i], i);
}
return {g[n], kc[n]};
}
long long 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]);
vc2.push_back({r[i], c[i]});
}
sort(vc2.begin(), vc2.end(), [](pii a, pii b){
if(a.ff == b.ff) return a.ss > b.ss;
return a.ff < b.ff;
});
pii lst = {-1, -1};
for(int i = 0; i < n; i++){
if(vc2[i].ss > lst.ss){
vc.push_back(vc2[i]);
lst = vc2[i];
}
}
ll l = 0, rr = 1LL*m*m;
//k = min(k, vc.size());
while(l <= rr){
ll m = (l + rr) / 2;
pll ans = check(m);
//cerr<<m<<" "<<ans.ff<<" "<<ans.ss<<endl;
if(ans.ss <= k){
rr = m - 1;
}else{
l = m + 1;
}
}
pll ans = check(l);
assert(ans.ss <= k);
return ans.ff - k*l;
}
