#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Car {
ll t, w;
Car(ll _t, ll _w) : t(_t), w(_w) { }
Car() { }
};
ll l, x;
int n, m;
vector<ll> s;
vector<Car> cars;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L, x = X;
n = N, m = M;
cars.resize(n);
for (int i = 0; i < n; i++) {
cars[i] = Car(T[i], W[i]);
}
s.assign(S.begin(), S.end());
return;
}
ll arrival_time(ll Y) {
ll start = Y, arrive;
vector<Car> cars_cur = cars;
vector<Car> cars_nxt(n);
for (int i = 1; i < m; i++) {
sort(cars_cur.begin(), cars_cur.end(), [](Car c1, Car c2) {
return make_pair(c1.t, c1.w) < make_pair(c2.t, c2.w);
});
arrive = start + x * (s[i] - s[i - 1]);
for (int j = 0; j < m; j++) {
cars_nxt[j] = cars_cur[j];
cars_nxt[j].t = cars_cur[j].t + cars_nxt[j].w * (s[i] - s[i - 1]);
if (j) cars_nxt[j].t = max(cars_nxt[j].t, cars_nxt[j - 1].t);
if (cars_cur[j].t < start) arrive = max(arrive, cars_nxt[j].t);
}
swap(cars_cur, cars_nxt);
start = arrive;
}
return start;
}
