#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=1e3+5;
vector<ll> w, s;
ll m, speed;
struct info
{
ll reachtime, idx, nxt;
info(ll reachtime, ll idx): reachtime(reachtime), idx(idx) {}
ll nextstationtime(ll gap) {return reachtime+gap*w[idx];}
bool operator< (const info &o) const {return reachtime==o.reachtime?w[o.idx]>w[idx]:reachtime<o.reachtime;}
};
vector<info> t[nx];
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
m=M;
speed=X;
for (auto x:W) w.push_back(x);
for (auto x:S) s.push_back(x);
for (int i=0; i<N; i++) if (w[i]>X) t[0].push_back(info(T[i], i));
for (int i=0; i<m-1; i++)
{
sort(t[i].begin(), t[i].end());
ll mx=0;
for (auto &x:t[i])
{
mx=max(mx, x.nextstationtime(S[i+1]-S[i]));
x.nxt=mx;
t[i+1].push_back({mx, x.idx});
}
}
}
long long arrival_time(long long Y)
{
for (int i=0; i<m-1; i++)
{
if (t[i].empty()||t[i][0].reachtime>=Y)
{
// cout<<"debug "<<i<<' '<<s[i+1]-s[i]<<'\n';
Y+=(s[i+1]-s[i])*speed;
continue;
}
int l=0, r=t[i].size()-1;
while (l<r)
{
int md=(l+r+1)/2;
if (t[i][md].reachtime<Y) l=md;
else r=md-1;
}
Y=max(Y+(s[i+1]-s[i])*speed, t[i][l].nxt);
}
return Y;
}
