#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
ll x, n, m, l;
vector<ll> w, t, s;
vector<vector<ll>> dp;
void init(int _l, int _n, vector<ll> _t, vi _w, int _x, int _m, vi _s) {
n = _n; m = _m; x = _x; l = _l; t = _t;
w = vector<ll>(_w.begin(), _w.end());
s = vector<ll>(_s.begin(), _s.end());
dp.resize(m, vector<ll>(n));
dp[0] = t;
vector<pair<ll, int>> srt(n);
for (int i = 0; i < n; i++) {
srt[i] = {dp[0][i], i};
}
sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
if (_i.first == _j.first) return w[_i.second] < w[_j.second];
return _i.first < _j.first;
});
for (int j = 1; j < m; j++) {
ll ma = 0;
for (auto [tm, i]: srt) {
ma = max(ma, dp[j - 1][i] + w[i] * (s[j] - s[j - 1]));
dp[j][i] = ma;
}
for (int i = 0; i < n; i++) {
srt[i] = {dp[j][i], i};
}
sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
if (_i.first == _j.first) return w[_i.second] < w[_j.second];
return _i.first < _j.first;
});
}
}
ll arrival_time(ll y) {
priority_queue<pair<ll, int>> pq;
ll time = y;
ll ma = time;
for (int i = 0; i < n; i++) {
if (w[i] <= x) continue;
if (t[i] >= y) continue;
int j = 0;
for (int k = 1 << 14; k; k >>= 1) {
if (j + k < m && dp[j + k][i] < y + x * s[j + k]) {
j += k;
}
}
if (++j == m) continue;
pq.push({-j, i});
}
for (int j = 1; j < m; j++) {
time += x * (s[j] - s[j - 1]);
while (!pq.empty()) {
auto [_, i] = pq.top();
if (dp[j][i] >= time) {
pq.pop();
time = dp[j][i];
} else {
break;
}
}
}
return time;
}
