#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<pair<ll, int>> loc[1000];
ll dp[1000][1000]; // time train j arrives at i+1
vector<ll> T;
vector<int> W, S;
int X, L, N, M;
void init(int l, int n, std::vector<long long> t, std::vector<int> w, int x, int m, std::vector<int> s) {
X = x, L = l, N = n, M = m;
T = t, W = w, S = s;
for (int i = 0; i < N; i ++) {
loc[0].push_back({T[i], i});
}
for (int i = 0; i < M-1; i ++) {
sort(loc[i].begin(), loc[i].end(), [&](const pair<ll, int> a, const pair<ll, int> b) {
if (a.first != b.first) return a.first < b.first;
return W[a.second] < W[b.second];
});
ll worst = 0;
for (auto [a, b]:loc[i]) {
worst = max(worst, (ll)W[b]*(S[i+1] - S[i]) + a);
dp[i][b] = worst;
loc[i+1].push_back({worst, b});
}
loc[i].push_back({1e9, -1});
}
// for (int i = 0; i < M; i ++) {
// cout << "At station " << i << ":\n";
// for (auto [a, b]:loc[i]) {
// cout << a << ": ";
// for (int j:b) {
// cout << j << " ";
// }
// cout << "\n";
// }
// }
}
ll arrival_time(ll Y) {
for (int i = 0; i < M-1; i ++) {
// find the relevant one
int low = 0, high = N;
while (high > low) {
int mid = (low + high)/2;
if (loc[i][mid].first >= Y) high = mid;
else low = mid + 1;
}
if (low == 0) {
// if it's the first bus, can travel until the end
return (ll)X*(L - S[i]) + Y;
}
auto [a, b] = loc[i][low-1];
Y = max((ll)X*(S[i+1] - S[i]) + Y, dp[i][b]);
}
return Y;
}
// int main() {
// init(6, 4, {20, 10, 40, 0}, {5, 20, 20, 30}, 10, 4, {0, 1, 3, 6});
// cout << arrival_time(0) << "\n" << arrival_time(50);
// }
