#include "overtaking.h"
#include <bits/stdc++.h>
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
int n,X,m;
vector<pair<int,int>> b;
vector<vector<int>> s; // time of bus i a la station j
vector<vector<pair<int,int>>> sb; // sorted array of busses i at station
vector<vector<int>> dp; // when it will arrive if it collides at n
vector<int> a;
vector<pair<pair<int,int>,int>> fseg;
void init(signed L, signed N, std::vector<long long> T, std::vector<signed> W, signed _x, signed M, std::vector<signed> _s)
{
n=N; X=_x; m=M;
a.resize(m+1);
sb.resize(m+1);
a[m]=L;
for (int i = 0; i < m; i++) a[i]=_s[i];
for (int i = 0; i < n; i++) {
if(W[i]<X) continue;
b.push_back({W[i],T[i]});
}
n=sz(b);
s.resize(n, vector<int>(m+1));
sort(rall(b));
for (int i = 0; i < n; i++) { sb[0].push_back({b[i].second,i}); s[i][0]=b[i].second; }
for (int i = 1; i < m; i++)
{
sort(all(sb[i-1]));
int mx=0;
int cmx=0;
for (int j = 0; j < n; j++)
{
int x=sb[i-1][j].second;
if(j>0&&sb[i-1][j].first!=sb[i-1][j-1].first){
mx=max(mx,cmx);
cmx=mx;
}
s[x][i]=max(mx,sb[i-1][j].first+b[x].first*(a[i]-a[i-1]));
cmx=max(s[x][i],cmx);
sb[i].push_back({s[x][i],x});
}
}
vector<pair<int,pair<int,int>>> seg;
for (int i = m-1; i > 0; i--)
{
for (int j = 0; j < n; j++)
{
int x=sb[i-1][j].second;
int xd=a[m]-a[i];
int _l=s[x][i]-(X*a[i]),r=s[x][i-1]-(X*a[i-1]),w=s[x][i]+X*xd;
seg.push_back({w,{_l,r}});
}
}
unordered_map<int,int> comp;
unordered_map<int,int> decomp;
set<int> st;
for (int i = 0; i < sz(seg); i++)
{
st.insert(seg[i].second.first);
st.insert(seg[i].second.second);
}
int j=0;
for (auto u : st)
{
comp[u]=j;
decomp[j]=u;
j++;
}
vector<vector<int>> event(j);
for (int i = 0; i < sz(seg); i++){
event[comp[seg[i].second.first]].push_back(i);
event[comp[seg[i].second.second]].push_back(-(i+1));
}
priority_queue<pair<int,int>> pq;
vector<bool> rem(sz(seg),false);
int lmx=-1;
int lI=0;
for (int i = j-1; i >= 0; i--)
{
for (auto u : event[i])
{
if(u<0) rem[abs(u)-1]=true;
else pq.push({seg[u].first,u});
}
while(!pq.empty()){
if(rem[pq.top().second]) pq.pop();
else break;
}
if(pq.empty()){
if(lmx>-1) fseg.push_back({{decomp[lI],decomp[i]},lmx});
lmx=-1;
}else if(lmx!=pq.top().first){
if(lmx>-1){
fseg.push_back({{decomp[lI],decomp[i]},lmx});
}
lmx=pq.top().first;
lI=i;
}
}
sort(rall(fseg));
return;
}
long long arrival_time(long long Y)
{
int l=0; int r=sz(fseg)-1;
int ans=-1;
while(l<=r){
int mid=(l+r)/2;
if(fseg[mid].first.first>=Y){
ans=mid;
l=mid+1;
}else{
r=mid-1;
}
}
if(ans==-1||fseg[ans].first.second>=Y) return (a[m]*X);
return fseg[ans].second;
}
