#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
struct Line{
int id;
ll x, y, g;
Line(int _id, int _x, int _y, int _g){
id = _id;
x = _x;
y = _y;
g = _g;
}
ll cross(ll y_, ll g_){
ll dy = y - y_;
ll dg = g - g_;
return dy / dg + (dy % dg != 0);
}
ll query(ll xx){
return y - g * xx;
}
};
int cnt[100005];
ll ans[100005];
vector<Line> line;
int n;
vector<pair<int, int> > tmp, a;
bool ooo = 0;
void calc(ll c){
line.clear();
int it = 0, sz = 0;
line.push_back(Line(0, 0, a[1].ff * a[1].ff, 2 * a[1].ff));
for(int i = 1; i <= n; i++){
while(it < sz && line[it + 1].x <= a[i].ss)
it++;
ans[i] = line[it].query(a[i].ss) + c + a[i].ss * a[i].ss;
cnt[i] = cnt[line[it].id] + 1;
if(i == n) break;
ll xx = max(0, a[i].ss - a[i + 1].ff);
ll yy = ans[i] + a[i + 1].ff * a[i + 1].ff - xx * xx;
ll gg = 2 * a[i + 1].ff;
while(sz >= 0 && line[sz].cross(yy, gg) <= line[sz].x){
line.pop_back();
sz--;
}
sz++;
line.push_back(Line(i,
sz == 0 ? 0 : line[sz - 1].cross(yy, gg),
yy,
gg));
it = min(it, sz);
}
}
ll take_photos(int n, int qq, int k, std::vector<int> rr, std::vector<int> c) {
for(int i = 0; i < n; i++)
tmp.push_back({min(rr[i], c[i]), -max(c[i], rr[i])});
int mxm = -1;
sort(tmp.begin(), tmp.end());
a.push_back({-1, -1});
if(ooo)cout<<'\n';
for(auto& x : tmp){
if(mxm < -x.ss){
a.push_back({x.ff, 1 - x.ss});
mxm = -x.ss;
}
}
::n = n = a.size() - 1;
ll l = 0, r = qq * qq;
while(l < r){
ll m = (l + r) >> 1;
calc(m);
if(cnt[n] <= k) r = m;
else l = m + 1;
}
calc(r);
return ans[n] - cnt[n] * r;
}
