#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> t;
vector<int> w;
vector<int> s;
int l;
int n;
int x;
int m;
vector<vector<ll>> arrival;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
l = L;
n = N;
t = T;
w = W;
s = S;
x = X;
m = M;
}
long long arrival_time(long long Y) {
vector<ll> T = t;
vector<int> W = w;
vector<int> S = s;
int L = l;
int N = n + 1;
int X = x;
int M = m;
T.push_back(Y);
W.push_back(X);
arrival.clear();
arrival.resize(M, vector<ll>(N));
arrival[0] = T;
for(int i = 1; i < M; i++) {
vector<tuple<ll, int, ll, int>> expected(N); // departure, speed, arrival, node
int distance = s[i] - s[i - 1];
for(int j = 0; j < N; j++) {
expected[j] = make_tuple(arrival[i - 1][j], W[j], arrival[i - 1][j] + 1ll * W[j] * distance, j);
}
sort(expected.begin(), expected.end());
for(int j = 1; j < N; j++) {
tuple<ll, int, ll, int> t = expected[j];
expected[j] = make_tuple(get<0>(t), get<1>(t), max(get<2>(t), get<2>(expected[j - 1])), get<3>(t));
}
for(int j = 0; j < N; j++) {
arrival[i][get<3>(expected[j])] = get<2>(expected[j]);
}
}
return arrival[M - 1][N - 1];
}
