#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int L, N;
vector<ll> T;
vector<int> W;
int X, M;
vector<int> S;
void init(int _L, int _N, vector<ll> _T, vector<int> _W, int _X, int _M, vector<int> _S) {
L = _L; N = _N; T = _T; W = _W; X = _X; M = _M; S = _S;
}
ll arrival_time(ll Y) {
vector<ll> dp = T;
dp.push_back(Y);
for (int i = 1; i < M; i++) {
vector<array<ll, 3>> tmp(N+1);
for (int j = 0; j < N; j++) tmp[j] = {dp[j], dp[j] + (ll)W[j]*(S[i]-S[i-1]), j};
tmp[N] = {dp[N], dp[N] + (ll)X*(S[i]-S[i-1]), N};
sort(tmp.begin(), tmp.end());
ll mxt = 0;
for (int j = 0; j <= N; j++) {
mxt = max(mxt, tmp[j][1]);
dp[tmp[j][2]] = mxt;
}
}
return dp[N];
}
