#include "aliens.h"
#include <bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
const double E = 0.001;
struct Line{
int id;
double x, y, g;
Line(int _id, int _x, int _y, int _g){
id = _id;
x = _x;
y = _y;
g = _g;
}
double cross(double y_, double g_){
return (y - y_) / (g - g_);
}
double query(double xx){
return y - g * xx;
}
};
int cnt[100005];
double ans[100005];
vector<Line> line;
int n;
vector<pair<int, int> > tmp, a;
void calc(double c){
line.clear();
int it = 0, sz = 0;
line.push_back(Line(0, 0, ans[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;
double xx = max(0, a[i + 1].ff - a[i].ss);
double yy = ans[i] + a[i + 1].ff * a[i + 1].ff - xx * xx;
double 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);
}
}
long long 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});
for(auto& x : tmp){
if(mxm < -x.ss){
a.push_back({x.ff, 1-x.ss});
mxm = -x.ss;
}
}
::n = n = a.size() - 1;
double l = 0, r = 1000000000;
while(l + E < r){
double m = (l + r) / 2;
calc(m);
if(cnt[n] <= k) r = m;
else l = m;
}
calc(r);
return (long long)ans[n] - cnt[n] * l;
}
