#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, k; ll L, base_speed;
ll start[1002], speed[1002], arr[1002];
map<ll, ll> mp;
ll stop[1002][1002];
void init(int _L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
L = _L, base_speed = X;
for(int i=0; i<N; i++){
if(W[i] <= X) continue;
++n;
start[n] = T[i], speed[n] = W[i] - X;
}
k = M;
for(int i=1; i<=k; i++) arr[i] = S[i-1];
vector<int> order;
for(int i=1; i<=n; i++) order.push_back(i);
sort(order.begin(), order.end(), [&](int a, int b){
return speed[a] > speed[b];
});
for(int i=1; i<=n; i++) stop[1][i] = start[i];
for(int d=2; d<=k; d++){
map<ll, ll> mp;
for(int x: order){
ll v = stop[d-1][x] + (arr[d] - arr[d-1]) * speed[x];
auto it = mp.lower_bound(stop[d-1][x]);
if(it != mp.begin()) v = max(v, prev(it)->second);
stop[d][x] = v;
if(mp.count(stop[d-1][x]) == 0 || mp[stop[d-1][x]] < stop[d][x]) mp[stop[d-1][x]] = stop[d][x];
}
}
mp[-1] = -1;
mp[ll(4e18)] = ll(4e18);
for(int d=k; d>=2; d--){
vector<pair<ll, ll> > vec;
for(int i=1; i<=n; i++) vec.push_back(make_pair(stop[d-1][i], stop[d][i]));
sort(vec.begin(), vec.end());
for(int i=0; i<(int)vec.size(); i++){
if(i+1 < (int)vec.size() && vec[i].first == vec[i+1].first) continue;
// if(i && vec[i-1].second == vec[i].second) continue;
ll x = vec[i].first, y = vec[i].second;
auto it = mp.lower_bound(x);
ll yv = max(y, prev(mp.lower_bound(y))->second);
while(it->second <= yv){
++it;
mp.erase(prev(it));
}
mp[x] = max(mp[x], yv);
}
// printf("d = %d\n", d);
// for(auto [x, y]: mp) printf("(%lld, %lld) ", x, y);
// puts("");
}
}
ll arrival_time(ll Y){
ll yv = max(Y, prev(mp.lower_bound(Y))->second);
return yv + L * base_speed;
}
