#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
struct Bus {
int t;
int w;
bool operator<(const Bus& other) {
return t == other.t ? (w < other.w) : (t < other.t);
}
};
int N, M, X, L;
vec<int32_t> S;
const int MXM = 1'005;
const int MXN = 1'005;
const int MXQ = 1'000'005;
vec<Bus> buses_arvs[MXM];
int arrival_mem[MXM][MXN];
int arrival(int i, int y) {
if(i == M-1) {
//cerr << "HERE: " << y << '\n';
return y;
}
Bus b{y, 0};
auto it = lower_bound(buses_arvs[i].begin(), buses_arvs[i].end(), b);
int blow_i = (it-buses_arvs[i].begin())-1;
//cerr << blow_i << '\n';
if(blow_i == -1) {
return y;
}
int l = i+1;
int r = M;
while(l < r) {
int j = (l+r-1)/2;
if(b < buses_arvs[j][blow_i]) {
r = j+1;
if(l + 1 == r) break;
}
else {
l = j+1;
}
}
if(l == M) {
assert(l==r);
return y;
}
int j = l;
//cerr << "J: " << j << '\n';
if(arrival_mem[j][blow_i] == -1) {
arrival_mem[j][blow_i] = arrival(j, buses_arvs[j][blow_i].t);
}
return arrival_mem[j][blow_i];
}
void init(int32_t L, int32_t N, std::vector<long long> T, std::vector<int32_t> W, int32_t X, int32_t M, std::vector<int32_t> S)
{
memset(arrival_mem, -1, sizeof(arrival_mem));
::L = L; ::N = N; ::M = M; ::X = X; ::S = S;
buses_arvs[0] = vec<Bus>(0);
for(int i = 0; i<N; i++) {
if(W[i] > X) {
buses_arvs[0].push_back({T[i], W[i]-X});
}
}
N = buses_arvs[0].size();
sort(buses_arvs[0].begin(), buses_arvs[0].end());
for(int i = 1; i<M; i++) {
int mxt = 0;
buses_arvs[i] = vec<Bus>(N);
for(int j = 0; j<N; j++) {
mxt = max(buses_arvs[i-1][j].t + buses_arvs[i-1][j].w * (S[i]-S[i-1]), mxt);
buses_arvs[i][j] = {mxt, buses_arvs[i-1][j].w};
}
sort(buses_arvs[i].begin(), buses_arvs[i].end());
}
return;
}
long long arrival_time(long long Y)
{
return arrival(0, Y) + L*X;
}
