// ~ Be Name Khoda ~ //
#include "aliens.h"
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e5 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int n;
vector <pair<ll, ll>> av;
pair <ll, int> dp[maxn5];
namespace cht{
int pt = 0, best;
pair <ll, pair<pair<ll, int>, ll>> a[maxn5]; // {st, {cons, shib}}
ll last = inf;
void clear(){
pt = 0;
best = 0;
last = inf;
}
ll inter(pair <pair<ll, int>, ll> a, pair <pair<ll, int>, ll> b){
if(b.se == a.se)
return a.fi > b.fi ? inf : -inf;
return (a.fi.fi - b.fi.fi) / (b.se - a.se) + ((a.fi.fi - b.fi.fi) % (b.se - a.se) > 0 || ((a.fi.fi - b.fi.fi) % (b.se - a.se) == 0 && b.fi.se < a.fi.se));
}
void add(pair<ll, int> cons, ll x){
while(pt && inter(a[pt - 1].se, {cons, x}) <= a[pt - 1].fi)
pt--;
a[pt] = {-inf, {cons, x}};
if(pt)
a[pt].fi = inter(a[pt - 1].se, a[pt].se);
pt++;
//cout << "WA " << a[best + 1].fi << ' ' << a[pt - 1].fi << endl;
//cout << "added " << pt << ' ' << best << ' ' << last << ' ' << a[pt - 1].fi << ' ' << a[best].fi << ' ' << a[best + 1].fi << ' ' << a[pt - 1].se.fi << ' ' << a[pt - 1].se.se << endl;
}
pair <ll, int> get_max(ll x){
best = min(best, pt - 1);
//cout << "here " << best << ' ' << a[best].fi << ' ' << x << endl;
while(best + 1 < pt && a[best + 1].fi <= x)
best++;
//cout << "in " << x << ' ' << best << endl;
return mp(a[best].se.fi.fi + a[best].se.se * x, a[best].se.fi.se);
}
}
pair <ll, int> check(ll y){
//cout << "********** " << x << endl;
cht::clear();
cht::add(mp(-(av[0].fi * av[0].fi), 0), av[0].fi);
for(int i = 0; i < n; i++){
auto ans = cht::get_max(2 * (av[i].se + 1));
dp[i] = {(av[i].se + 1) * (av[i].se + 1) - ans.fi + y, (-ans.se) + 1};
//cout << "hey " << i << ' ' << dp[x][i] << endl;
if(i + 1 < n)
cht::add(mp(-(dp[i].fi + av[i + 1].fi * av[i + 1].fi - (av[i].se >= av[i + 1].fi ? (av[i].se - av[i + 1].fi + 1) * (av[i].se - av[i + 1].fi + 1) : 0)), -dp[i].se), av[i + 1].fi);
}
return dp[n - 1];
}
vector <pair<int, int>> pt;
bool rem[maxn5];
long long take_photos(int N, int m, int k, std::vector<int> r, std::vector<int> c) {
n = N;
//*
for(int i = 0; i < n; i++)
pt.pb({min(r[i], c[i]), max(r[i], c[i])});
sort(all(pt));
for(int i = 0; i < n; i++){
while(av.size() && av.back().fi == pt[i].fi && av.back().se <= pt[i].se)
av.pop_back();
if(av.size() && av.back().se >= pt[i].se)
continue;
av.pb(pt[i]);
}
n = av.size();
//*/
/*
for(int i = 0; i < n; i++)
cout << av[i].fi << ' ' << av[i].se << endl;
//*/
ll lo = -1, hi = inf;
while(hi - lo > 1){
ll mid = (lo + hi) >> 1;
if(check(mid).se <= k)
hi = mid;
else
lo = mid;
}
auto ans = check(hi);
return ans.fi - hi * k;
}
