#include "bits/stdc++.h"
#include "overtaking.h"
#define pb push_back
using namespace std;
const int MAXN = 1e3 + 5;
vector<vector<long long> > t(MAXN, vector<long long>(MAXN));
vector<int> s, w;
vector<long long> st;
int n, m, x;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S){
for(int i = 0; i < N; i++){
t[i][0] = T[i];
}
for(int j = 1; j < M; j++){
vector<long long> ep(N);
for(int i = 0; i < N; i++){
ep[i] = t[i][j-1] + W[i] * (S[j] - S[j-1]);
}
for(int i = 0; i < N; i++){
long long mval = ep[i];
for(int cek = 0; cek < N; cek++){
if(t[cek][j-1] < t[i][j-1]){
mval = max(mval, ep[cek]);
}
}
t[i][j] = mval;
}
}
s = S;
n = N;
m = M;
x = X;
w = W;
st = T;
}
long long arrival_time(long long Y){
for(int i = 0; i < n; i++){
t[i][0] = st[i];
}
t[n][0] = Y;
for(int j = 1; j < m; j++){
vector<long long> ep(n+1);
for(int i = 0; i < n; i++){
ep[i] = t[i][j-1] + w[i] * (s[j] - s[j-1]);
}
ep[n] = t[n][j-1] + x * (s[j] - s[j-1]);
for(int i = 0; i <= n; i++){
long long mval = ep[i];
for(int cek = 0; cek <= n; cek++){
if(t[cek][j-1] < t[i][j-1]){
mval = max(mval, ep[cek]);
}
}
t[i][j] = mval;
}
}
return t[n][m-1];
}
