#include <bits/stdc++.h>
using namespace std;
using ll = long long;
map<ll, vector<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][T[i]].push_back(i);
}
for (int i = 0; i < M-1; i ++) {
ll worst = 0;
for (auto &[a, b]:loc[i]) {
sort(b.begin(), b.end(), [&](const int a, const int b) {
// sort by increasing gradient
return W[a] < W[b];
});
for (int j:b) {
worst = max(worst,(ll)W[j]*(S[i+1] - S[i]) + a);
dp[i][j] = worst;
loc[i+1][worst].push_back(j);
}
}
}
// 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
auto it = loc[i].lower_bound(Y);
if (it == loc[i].begin()) {
// if it's the first bus, can travel until the end
return (ll)X*(L - S[i]) + Y;
}
it --;
auto [a, b] = *it;
Y = max((ll)X*(S[i+1] - S[i]) + Y, dp[i][b.back()]);
}
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);
// }
