#include <bits/stdc++.h>
#include "overtaking.h"
#define sz(x) (int)(size(x))
using namespace std;
using ll = long long;
constexpr ll inf = 2e18;
struct Segment{
ll l, r, y1, y2;
Segment(ll l_=0, ll r_=0, ll y1_=0, ll y2_=0):l(l_),r(r_),y1(y1_),y2(y2_){}
ll eval(ll x)const{
return y1 + (x-l)*((y2-y1)/(r-l));
}
Segment cut(ll cl, ll cr)const{
ll nl = max(l, cl);
ll nr = min(r, cr);
ll ny1 = eval(nl);
ll ny2 = eval(nr);
return {nl, nr, ny1, ny2};
};
bool operator<(const Segment& o)const{
if(l < o.l) return true;
if(l > o.l) return false;
return r < o.r;
}
};
using Fun = vector<Segment>;
Fun merge(const Fun& f, const Fun& g){ // g(f(x))
Fun res;
int i = 0;
for(Segment s : f){
while(i < sz(g) && g[i].r <= s.y1) i++;
if(s.y1 == s.y2){
ll y = g[i].eval(s.y1);
res.emplace_back(s.l, s.r, y, y);
}
else{
while(i < sz(g)){
Segment seg = g[i].cut(s.y1, s.y2);
ll offset = s.l - s.y1;
seg.l += offset, seg.r += offset;
res.push_back(seg);
if(seg.r < s.r) i++;
else break;
}
}
}
return res;
}
vector<Fun> funs;
Fun myFun;
Fun dcMerge(int l, int r){
if(l+1 == r) return funs[l];
int m = (l+r)/2;
Fun f = dcMerge(l, m);
Fun g = dcMerge(m, r);
return merge(f, g);
}
ll funEval(const Fun& f, ll x){
auto it = --lower_bound(f.begin(), f.end(), Segment{x+1, x+1, 0, 0});
return it->eval(x);
}
void dbg(const Fun& f){
for(Segment s : f){
cerr << s.l << " " << s.r << " " << s.y1 << " " << s.y2 << "\n";
}
cerr << "\n";
}
int L, M;
ll X;
vector<vector<pair<ll, ll>>> v;
vector<int> S;
void init(int Lin, int N, vector<ll> T, vector<int> W, int Xin, int Min, vector<int> Sin){
L = Lin, M = Min, X = Xin, S = Sin;
vector<int> ord(N);
for(int i = 0; i < N; i++) ord[i] = i;
sort(ord.begin(), ord.end(), [&](int i, int j){return T[i] < T[j];});
v.resize(M);
for(int i : ord){
if(W[i] <= X) continue;
if(v[0].empty()) v[0].emplace_back(T[i], (ll)W[i]);
else v[0].emplace_back(T[i], (ll)W[i]);
}
sort(v[0].begin(), v[0].end());
for(int k = 1; k < M; k++){
ll d = S[k]-S[k-1];
ll lt1 = -1, lt2 = 0;
Fun f;
auto addSeg = [&](ll t){
if(lt1 < t){
ll spl = min(t+1, max(lt1+1, lt2 - X*d));
if(spl > lt1+1) f.emplace_back(lt1+1, spl, lt2, lt2);
if(spl <= t) f.emplace_back(spl, t+1, spl + X*d, t+1 + X*d);
}
};
for(auto [t, w] : v[k-1]){
ll e = t+w*d;
ll t2 = max(lt2, e);
v[k].emplace_back(t2, w);
addSeg(t);
lt1 = t, lt2 = t2;
}
sort(v[k].begin(), v[k].end());
addSeg(inf);
funs.push_back(f);
// dbg(f);
}
myFun = dcMerge(0, M-1);
// dbg(myFun);
}
ll arrival_time(ll Y){
return funEval(myFun, Y);
// ll t = Y;
// for(int k = 0; k < M-1; k++){
// t = funEval(funs[k], t);
// }
// return t;
}
