#include "overtaking.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
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});
}
}
// for (int i=0; i<m-1; i++) for (int j=0; j<t[i].size(); j++) cout<<"debug "<<i<<' '<<j<<' '<<t[i][j].reachtime<<' '<<t[i][j].idx<<'\n';
}
long long arrival_time(long long Y)
{
if (t[0].empty()) return s[m-1]*speed;
int idx=t[0].size()-1;
for (int i=0; i<m-1; i++)
{
while (idx>=0&&t[i][idx].reachtime>=Y) idx--;
if (idx<0) return Y+(s[m-1]-s[i])*speed;
Y=max(Y+(s[i+1]-s[i])*speed, t[i][idx].nxt);
// cout<<"idx "<<idx<<'\n';
// cout<<"debug "<<i<<' '<<Y<<'\n';
}
return Y;
}
