#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> w, s;
vector<vector<long long>> when;
long long x;
void init(int l, int N, vector<long long> t, vector<int> W, int X, int M, vector<int> S) {
n = N; m = M; x = X; w = W; s = S;
when = vector<vector<long long>>(m, vector<long long>(n));
when[0] = t;
for (int i = 1; i < m; i++) {
vector<int> order(n);
iota(order.begin(), order.end(), 0);
sort(order.begin(), order.end(), [&](int a, int b) {
if (when[i - 1][a] != when[i - 1][b]) {
return when[i - 1][a] < when[i - 1][b];
} else {
return w[a] < w[b];
}
});
long long mx = 0;
for (int j = 0; j < n; j++) {
int b = order[j];
mx = max(mx, when[i - 1][b] + w[b] * 1LL * (s[i] - s[i - 1]));
when[i][b] = mx;
}
}
return;
}
long long arrival_time(long long y) {
for (int i = 0; i + 1 < m; i++) {
long long t = y + x * 1LL * (s[i + 1] - s[i]);
for (int j = 0; j < n; j++) {
if (when[i][j] >= y) {
continue;
}
t = max(t, when[i + 1][j]);
}
y = t;
}
return y;
}
