#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
int road_length;
int nbuses;
vector<long long> times;
vector<int> speeds;
int rtime;
int m;
vector<int> stations;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S) {
road_length = L;
nbuses = N;
times = T;
speeds = W;
rtime = X;
m = M;
stations = S;
}
long long arrival_time(long long Y) {
vector<long long> t(nbuses + 1);
for (int i = 0; i < nbuses; i++)
t[i] = times[i];
t[nbuses] = Y;
for (int i = 1; i < m; i++) {
vector<long long> e(nbuses + 1);
for (int j = 0; j <= nbuses; j++) {
if (j == nbuses)
e[j] = t[j] + 1ll * rtime * (stations[i] - stations[i - 1]);
else
e[j] = t[j] + 1ll * speeds[j] * (stations[i] - stations[i - 1]);
}
vector<long long> vals(nbuses + 1);
for (int j = 0; j <= nbuses; j++) {
vals[j] = e[j];
for (int k = 0; k <= nbuses; k++) {
if (t[k] < t[j])
vals[j] = max(vals[j], e[k]);
}
}
t = vals;
}
return t[nbuses];
}
