#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;
#define X first
#define Y second
#define mid ((l+r)>>1)
inline ll fdiv(ll a, ll b) {
bool sgn = 0;
if(a<0) {
sgn ^= 1;
a = -a;
}
if(b<0) {
sgn ^= 1;
b = -b;
}
return sgn ? - (a+b-1)/b : a/b;
}
inline ll isect(pll f, pll g) {
return fdiv(f.Y-g.Y, g.X-f.X);
}
inline ll eval(pll f, ll x) {
return f.X*x + f.Y;
}
struct cht : vector<pll> {
vector<ll> vec;
vector<int> id;
inline void add(pll ln, int id_) {
while(!empty()) {
vec.back() = isect(back(), ln);
if(vec.size()==1 || vec.back()>vec[vec.size()-2]) break;
vec.pop_back();
pop_back();
id.pop_back();
}
vec.push_back(1e9);
push_back(ln);
id.push_back(id_);
}
inline pll get(ll x) {
int pos = lower_bound(vec.begin(), vec.end(), x)-vec.begin();
return {eval((*this)[pos], x), id[pos]};
}
};
const int MXN = 1e5+5;
int n, L[MXN], R[MXN];
ll dp[MXN];
int cnt[MXN];
inline void add(cht &ds, int j) {
ll tmp = max(0, R[j]-L[j+1]+1);
ds.add({-2*L[j+1], dp[j] + 1ll*L[j+1]*L[j+1] - tmp*tmp}, j);
}
ll take_photos(int nn, int m, int k, vector<int> LL, vector<int> RR) {
for(int i=0; i<nn; i++)
if(LL[i]>RR[i])
swap(LL[i], RR[i]);
vector<int> ord(nn);
iota(ord.begin(), ord.end(), 0);
sort(ord.begin(), ord.end(), [&](int i, int j) {
return pll(LL[i], -RR[i]) < pll(LL[j], -RR[j]);
});
L[0] = R[0] = -1;
for(int i=0; i<nn; i++)
if(RR[ord[i]]>R[n]) {
L[++n] = LL[ord[i]];
R[n] = RR[ord[i]];
}
auto alien = [&](ll cost) -> pll {
cht ds;
add(ds, 0);
for(int i=1; i<=n; i++) {
pll d = ds.get(R[i]+1);
dp[i] = cost + 1ll*(R[i]+1)*(R[i]+1) + d.X;
cnt[i] = cnt[d.Y]+1;
if(i<n) add(ds, i);
}
return {dp[n], cnt[n]};
};
ll l=-1, r=1ll*m*m+1;
while(r-l>1)
(alien(mid).Y<=k ? r : l) = mid;
pll ans = alien(r);
return ans.X - k*r;
}
