#include <bits/stdc++.h>
#include "aliens.h"
#define F first
#define S second
#define pii pair<int, int>
#define pb push_back
#define pld pair<pair<ld, ll>, int>
using namespace std;
typedef long long ll;
typedef long double ld;
const int maxN = 1e5 + 10, maxK = 510;
const ll oo = 2e15;
ld dp[maxN];
ll f[maxN];
int n, l[maxN], r[maxN], par[maxN], ted[maxN];
vector <pii> que;
pld lines[maxN];
bool cmp(pii a1, pii a2)
{
if(a1.F != a2.F) return a1.F < a2.F;
return a1.S > a2.S;
}
ld barkhord(pld A, pld B)
{
return (ld)(B.F.F - A.F.F + A.F.S - B.F.S - 1) / (ld)(A.F.S - B.F.S);
}
int check(ld c, bool g = 0)
{
int sz = 0, ptr = 0;
ted[0] = 0, par[0] = -1;
for (int i=1; i<=n; i++)
{
ll x = 0;
if(i - 1 > 0) x = f[i - 2];
pld t = {{dp[i - 1] + (ll)l[i - 1] * l[i - 1] - x, -2LL * l[i - 1]}, i - 1};
while(sz >= 2 && barkhord(lines[sz - 2], lines[sz - 1]) <= barkhord(lines[sz - 1], t)) sz --;
lines[sz ++] = t;
ptr = min(ptr, sz - 1);
while(ptr + 1 < sz && barkhord(lines[ptr], lines[ptr + 1]) <= r[i - 1]) ptr++;
//cout << i << " ))))) " << " << " << r[i - 1] << lines[ptr].F.F << ',' << lines[ptr].F.S << endl;
dp[i] = (ld)r[i - 1] * r[i - 1] + lines[ptr].F.F + lines[ptr].F.S * r[i - 1] - c;
int _par = lines[ptr].S;
par[i] = _par;
ted[i] = 1 + ted[_par];
//cout << i << ',' << dp[i] << " : " << par[i] << ',' << ted[i] << endl;
}
if(g)
{
ll res = 0;
int curr = n;
while(curr > 0)
{
int p = par[curr];
res += 1LL * (r[curr - 1] - l[p]) * (r[curr - 1] - l[p]);
if(p) res -= f[p - 1];
curr = p;
}
return res;
}
return ted[n];
}
long long take_photos(int NN, int m, int k, std::vector<int> R, std::vector<int> c) {
n = NN;
if(n > maxN) return cout << 1/0 << endl, -1;
for (int i=0; i<n; i++)
{
if(R[i] <= c[i])
c[i] ++;
else R[i] ++;
que.pb({min(R[i], c[i]), max(R[i], c[i])});
}
sort(que.begin(), que.end(), cmp);
int mx = -1, cnt = 0;
for (int i=0; i<n; i++)
{
if(mx >= que[i].S) continue ;
else
{
l[cnt] = que[i].F, r[cnt] = que[i].S;
mx = max(mx, que[i].S);
cnt ++;
}
}
n = cnt;
//for (int i=0; i<n; i++) cout << l[i] << ',' << r[i] << endl; cout << endl;
ld lo = 0, hi = 2e12;
for (int i=0; i<n-1; i++)
if(r[i] > l[i + 1]) f[i] = 1LL * (r[i] - l[i + 1]) * (r[i] - l[i + 1]);
for (int i=0; i<300; i++)
{
ld mid = (lo + hi)/2;
if(check(mid) >= k) lo = mid;
else hi = mid;
}
//check(0, 1);
//cout << lo << endl;
return check(lo, 1);
}
