#include "aliens.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))
const ll MAXN = 1e5+100;
const ll INF = 1e18;
vector <pll> a;
pll dp[MAXN];
long long take_photos(int n, int m, int k, std::vector<int> R, std::vector<int> c) {
for (ll i = 0;i < n;i ++){
if (R[i] > c[i])swap(R[i],c[i]);
a.push_back(MP(R[i],c[i]));
}
sort(a.begin(),a.end(),[&](pll x,pll y){return MP(x.fi,-x.se) < MP(y.fi,-y.se);});
{
vector <pll> tmp;
for (ll i = 0;i < n;i ++){
if (tmp.empty()||a[i].se > tmp.back().se)tmp.push_back(a[i]);
}
swap(a,tmp);
}
n=sz(a);
ll l = 0,r = 1e18;
ll res = 1e18;
const ll mul = 1;
while (l <= r){
ll mid = (l + r) >> 1;
deque <pair <pll,ll> > cvh;
auto inter = [&](pll z1,pll z2){
//z1.fi * x + z1.se == z2.fi * x + z2.se
return (z2.se-z1.se)/(z1.fi-z2.fi)-1;
};
auto add = [&](ll y1,ll y2,ll y3) -> void{
pll x = MP(y1,y2);
while (sz(cvh) >=2 && inter(cvh[sz(cvh)-2].fi,cvh[sz(cvh)-1].fi) >= inter(cvh[sz(cvh)-1].fi,x)){
cvh.pop_back();
}
cvh.push_back(MP(x,y3));
};
auto eval = [&](ll x) -> pll{
assert(sz(cvh));
while (sz(cvh) >= 2 && MP(cvh[0].fi.fi * x + cvh[0].fi.se,cvh[0].se) > MP(cvh[1].fi.fi * x + cvh[1].fi.se,cvh[1].se))cvh.pop_front();
return MP(cvh[0].fi.fi * x + cvh[0].fi.se,cvh[0].se);
};
for (ll i = 0;i < n;i ++){
if (i)add(mul * (-2*a[i].fi),dp[i-1].fi+mul * (a[i].fi*a[i].fi-
(a[i-1].se >= a[i].fi ? (a[i-1].se-a[i].fi+1) * (a[i-1].se-a[i].fi+1) : 0)),
dp[i-1].se);
else add(mul*(-2*a[i].fi),mul*a[i].fi * a[i].fi,0);
pll tmp = eval(a[i].se+1);
dp[i].fi = tmp.fi + mul * (a[i].se+1)*(a[i].se+1) + mid;
dp[i].se = tmp.se + 1;
}
if (dp[n-1].se <= k){
// cout<<l<<' '<<r<<'\n';
r = mid - 1;
// cout<<mid<<' '<<dp[n-1].se<<' '<<dp[n-1].fi - dp[n-1].se * mid<<'\n';
res = dp[n-1].fi - k * mid;
}
else{
// cout<<l<<' '<<r<<'\n';
// cout<<dp[n-1].se<<'\n';
l = mid + 1;
}
}
return res/mul;
}
