#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long
#define ff first
#define ss second
const int N = 3005;
const ll INF = 1e18;
set<pair<ll, ll>> pref[N];
vector<ll> T, W, S;
ll n, m, x, L;
void init(int Ll, int nn, std::vector<long long> t, std::vector<int> w, int xx, int mm, std::vector<int> s)
{
L = Ll, n=nn, m=mm, x=xx;
for(int i = 0; i < n; ++i){
if(w[i] > x)
W.pb(w[i]), T.pb(t[i]);
}
for(int f: s) S.pb(f);
W.pb(x);
S.pb(Ll);
n = W.size();
vector<pair<ll, int>> F;
for(int i =0; i < n; ++i) F.pb({W[i], i});
sort(all(F));
reverse(all(F));
vector<vector<ll>> dp(n + 1, vector<ll>(m + 2));
for(int i = 0; i < n; ++i){
dp[i][0] = T[F[i].ss];
for(int j = 1; j <= m; ++j){
ll mx = dp[i][j - 1] + F[i].ff * (S[j] - S[j-1]);
auto pos = pref[j].lower_bound(pair<ll,ll>{dp[i][j - 1], -1});
if(pos == pref[j].begin()){
dp[i][j] = mx;
}else{
pos = prev(pos);
dp[i][j] = max(mx, (*pos).ss);
}
pref[j].insert({dp[i][j - 1], dp[i][j]});
}
}
return;
}
long long arrival_time(long long Y)
{
ll cur = Y;
for(int j = 1; j <= m; ++j){
ll mx = cur + x * (S[j] - S[j-1]);
auto pos = pref[j].lower_bound(pair<ll,ll>{cur, -1});
if(pos == pref[j].begin()){
cur = mx;
}else{
pos = prev(pos);
cur = max(mx, (*pos).ss);
}
}
return cur;
}
