#include "overtaking.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 3e5 + 10;
long long l, n, m, x, y;
vector < long long > t;
vector < int > w, s;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
l = L;
n = N;
t = T;
x = X;
w = W;
m = M;
s = S;
return;
}
struct bus
{
long long t, s, i;
bus(){};
bus(long long _t, long long _s, long long _i)
{
t = _t;
s = _s;
i = _i;
}
};
bus a[maxn];
bool cmp(bus b1, bus b2)
{
if(b1.t != b2.t)return (b1.t < b2.t);
return (b1.s < b2.s);
}
long long arrival_time(long long Y)
{
y = Y;
vector < bus > g;
for (int i = 0; i < n; ++ i)
{
long long t1 = t[i];
long long s1 = w[i];
if(t1 >= y)continue;
g.pb(bus(t1, s1, i));
}
long long arrive = y;
long long pre = s[0];
for (int i = 1; i < m; ++ i)
{
sort(g.begin(), g.end(), cmp);
long long dist = (s[i] - pre);
long long worst = 0;
long long exp_arrive = arrive + dist * x;
vector < bus > v;
for (auto &[t1, s1, nomer]: g)
{
long long arrived = max(worst, dist * s1 + t1);
worst = max(worst, arrived);
if(t1 <= arrive)exp_arrive = max(exp_arrive, worst);
v.pb(bus(arrived, s1, nomer));
}
g.clear();
for (auto &[t1, s1, nomer]: v)
{
if(t1 < exp_arrive)g.pb(bus(t1, s1, nomer));
}
arrive = max(exp_arrive, worst);
pre = s[i];
}
return arrive;
}
