#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
using ll = long long;
const int mxN = 1e3+10;
int l, n;vector<ll> t; vector<int> w; int x; int m; vector<int> s;
array<ll, 2> st[mxN][4*mxN];
void upd(int v, int node, int l, int r, int k, ll t, ll w) {
if(l == r && l == k) {
st[v][node] = {t, w};
return ;
}
if(l > k || r < k) return ;
int mid = (l+r)/2;
upd(v, node*2, l, mid, k, t, w);
upd(v, node*2+1, mid+1, r, k, t, w);
st[v][node] = max(st[v][node*2], st[v][node*2+1]);
}
int qry(int v, int node, int l, int r, ll x) {
if(l == r) return l;
int mid = (l+r)/2;
if(st[v][node*2][0] >= x) return qry(v, node*2, l, mid, x);
else return qry(v, node*2+1, mid+1, r, x);
}
ll qry1(int v, int node, int l, int r, int l1, int r1) {
if(l1 <= l && r <= r1) return st[v][node][0];
if(l1 > r || r1 < l) return 0;
int mid = (l+r)/2;
return max(qry1(v, node*2, l, mid, l1, r1), qry1(v, node*2+1, mid+1, r, l1, r1));
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L; n = N; t = T; w = W; x = X; m = M; s = S;
set<array<ll, 3>> buses;
for(int i = 0; i < n; i++) {
if(w[i] > x) buses.insert({t[i], w[i], i});
}
n = buses.size();
int idx = 0;
for(auto [t, w, _] : buses) {
upd(0, 1, 0, n-1, idx, t, w);
++idx;
}
for(int i = 1; i < m; i++) {
set<array<ll, 3>> nxt;
for(auto [t, w, idx] : buses) {
ll f = t + w * (s[i] - s[i-1]);
ll s;
if(nxt.empty()) s = 0;
else {
auto it = prev(nxt.end());
s = (*it)[0];
}
ll now = max(f, s);
nxt.insert({now, w, idx});
}
swap(buses, nxt);
idx = 0;
for(auto [t, w, _] : buses) {
upd(i, 1, 0, n-1, idx, t, w);
++idx;
}
}
}
ll calculate_arrival_time(ll Y) {
ll last = Y, cnt = Y > st[0][1][0] ? n : qry(0, 1, 0, n-1, Y);
for(int j = 1; j < m; j++) {
ll f = last + x * (s[j] - s[j-1]);
ll s = qry1(j, 1, 0, n-1, 0, cnt-1);
last = max(f, s);
cnt = last > st[j][1][0] ? n : qry(j, 1, 0, n-1, last);
if(j == m-1) return last;
}
}
ll arrival_time(ll Y) {
return calculate_arrival_time(Y);
}
