#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 1002
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int n, m, x;
vector<ll> d;
set<pll> r[MAXN];
ll t[MAXN][MAXN];
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S){
ll e;
vector<pii> w;
x = X, n = N, m = M;
for(int i = 0; i < n; i++){
w.append({W[i], i});
t[i][0] = T[i];
}
sort(all(w));
reverse(all(w));
for(int i = 0; i < m; i++)
d.append(S[i]);
for(auto & [s, i] : w){
if(s <= x) break;
for(int j = 0; j < m - 1; j++){
e = t[i][j] + s * (d[j + 1] - d[j]);
if(!r[j].empty() && (*r[j].begin()).ff < t[i][j])
e = max(e, (*(--r[j].lower_bound({t[i][j], 0}))).ss);
r[j].add({t[i][j], e});
t[i][j + 1] = e;
}
}
}
ll arrival_time(ll y){
ll e;
int s = x;
t[n][0] = y;
for(int j = 0; j < m - 1; j++){
e = t[n][j] + s * (d[j + 1] - d[j]);
if(!r[j].empty() && (*r[j].begin()).ff < t[n][j])
e = max(e, (*(--r[j].lower_bound({t[n][j], 0}))).ss);
t[n][j + 1] = e;
}
return t[n][m - 1];
}
