#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 3e18;
ll l, x;
int n, m;
vector<ll> s;
vector<vector<tuple<ll, ll, int>>> table;
vector<vector<ll>> et;
vector<vector<ll>> dp;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L, x = X;
m = M;
s.assign(S.begin(), S.end());
table.resize(m, vector<tuple<ll, ll, int>>(0));
for (int i = 0; i < N; i++) {
if (W[i] <= x) continue;
table[0].emplace_back(T[i], W[i], table[0].size());
}
n = table[0].size();
if (n == 0) return;
et.resize(m, vector<ll>(n));
for (int i = 0; i < n; i++) {
et[0][i] = get<0>(table[0][i]);
}
for (int i = 1; i < m; i++) {
sort(table[i - 1].begin(), table[i - 1].end());
table[i] = table[i - 1];
for (int j = 0; j < n; j++) {
auto &[t_nxt, w, idx] = table[i][j];
t_nxt = et[i - 1][idx] + w * (s[i] - s[i - 1]);
if (j) t_nxt = max(t_nxt, get<0>(table[i][j - 1]));
et[i][idx] = get<0>(table[i][j]);
}
}
sort(table[m - 1].begin(), table[m - 1].end());
dp.resize(m, vector<ll>(n, -1));
return;
}
ll calcT(ll y, int l, int r) {
return y + x * (s[r] - s[l - 1]);
}
int nextIntersection(ll y, int L, int k) {
int l = L + 1, r = m - 1;
while (r - l > 1) {
int mid = (l + r) / 2;
if (calcT(y, L + 1, mid) <= get<0>(table[mid][k])) r = mid;
else l = mid + 1;
}
for (int i = l; i <= r; i++) {
if (calcT(y, L + 1, i) <= get<0>(table[i][k])) return i;
}
return m;
}
void update(vector<pair<int, int>> &dp_empty, ll arrive) {
for (auto [i, k] : dp_empty) {
dp[i][k] = arrive;
}
}
ll arrival_time(ll y) {
if (table[0].empty()) return y + x * (s[m - 1] - s[0]);
int i = 0;
vector<pair<int, int>> empty_dp;
while (i < m) {
// cerr << "HELLO " << y << endl;
auto itr = lower_bound(table[i].begin(), table[i].end(), make_tuple(y, x, n));
if (itr == table[i].begin()) {
y = calcT(y, i + 1, m - 1);
break;
}
itr = prev(itr);
int k = itr - table[i].begin();
int i_nxt = nextIntersection(y, i, k);
if (i_nxt == m) {
y = calcT(y, i + 1, m - 1);
break;
}
// cerr << "WTF " << i_nxt << ' ' << calcT(y, i + 1, i_nxt) << ' ' << get<0>(table[i_nxt][k]) << endl;
if (dp[i_nxt][k] != -1) {
y = dp[i_nxt][k];
break;
}
empty_dp.emplace_back(i_nxt, k);
y = get<0>(table[i_nxt][k]);
i = i_nxt;
}
update(empty_dp, y);
// cerr << "ANSWER " << y << endl;
return y;
}
