#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int N, L;
vector<int> W, S;
int X, M;
vector<ll> T;
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;
M = _M;
N = _N;
T = _T;
W = _W;
X = _X;
S = _S;
W.push_back(X);
}
long long arrival_time(long long Y)
{
vector<vector<ll>> exp(N + 1, vector<ll>(M));
vector<int> ord(N + 1);
iota(begin(ord), end(ord), 0);
for (int i = 0; i < N; ++i) {
exp[i][0] = T[i];
}
exp[N][0] = Y;
for (int j = 1; j < M; ++j) {
sort(begin(ord), end(ord), [&](int x, int y){
if (exp[x][j - 1] != exp[y][j - 1]) return exp[x][j - 1] < exp[y][j - 1];
return W[x] < W[y];
});
ll tim = -1;
for (int it = 0; it <= N; ++it) {
int i = ord[it];
// cerr << W[i] << " ";
exp[i][j] = exp[i][j - 1] + W[i] * (S[j] - S[j - 1]);
exp[i][j] = max(tim, exp[i][j]);
tim = max(exp[i][j], tim);
}
// cerr << endl;
}
// cerr << Y << ":\n";
// for (int j = 0; j < M; ++j) {
// for (int i = 0; i <= N; ++i) {
// cerr << exp[i][j] << " ";
// }
// cerr << "\n";
// }
// cerr << "\n";
return exp[N][M - 1];
}
