#include "overtaking.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int> W, S;
vector<long long> T;
int L, N, X, M;
void init(int LL, int NN, std::vector<long long> TT, std::vector<int> WW, int XX, int MM, std::vector<int> SS)
{
L = LL; N = NN; X = XX; M = MM;
T = TT;
W = WW; S = SS;
return;
}
struct bus{
int w, n;
long long t;
bool operator <(const bus& a) const{
return (t < a.t || (a.t == t && w < a.w));
}
bool operator >(const bus& a) const{
return (t > a.t || (a.t == t && w > a.w));
}
};
long long arrival_time(long long Y)
{
long long ans(Y);
priority_queue< bus, vector<bus>, greater<bus> >q;
for (int i(0); i < N; i++) {
if (T[i] < Y) {
if (W[i] > X) {
bus a;
a.w = W[i];
a.t = T[i];
a.n = i;
q.push(a);
}
}
}
for (int i(1); i < M; i++) {
vector< int > blocked(N);
vector< bus > next;
if (q.empty()){
if (i == 1) ans += S[1] * X;
ans += (S[M - 1] - S[i]) * X;
break;
}
bus a = q.top(); q.pop();
long long latest(a.t + (S[i] - S[i - 1]) * a.w);
int blocking = a.n;
blocked[a.n] = a.n;
a.t = latest;
next.push_back(a);
while (!q.empty()) {
a = q.top(); q.pop();
if (a.t + (S[i] - S[i - 1]) * a.w <= latest) {
blocked[a.n] = blocking;
}
else {
latest = a.t + (S[i] - S[i - 1]) * a.w;
blocking = a.n;
blocked[a.n] = a.n;
}
a.t = latest;
next.push_back(a);
}
int overtoken(N);
if (ans + (S[i] - S[i - 1]) * X <= latest) {
overtoken = blocking;
ans = latest;
}
else ans += (S[i] - S[i - 1]) * X;
for (bus j : next) {
if (blocked[j.n] != overtoken) q.push(j);
}
}
return ans;
}
