// In the name of Allah
#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define F first
#define S second
#define endl '\n'
#define sep ' '
#define pb push_back
#define Mp make_pair
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
const int maxn = 1000 + 4;
const int maxs = (1 << 20) + 4;
const ll oo = 8e18 + 4;
int n, m; ll L, X;
pll A[maxn]; ll R[maxn]; int ind;
ll dp[maxn][maxn]; vector<ll> arr;
ll val[maxn][maxn]; vector<ll> ls[maxn];
pii t[2 * maxs];
bool cmp(int i, int j) {
return (dp[ind][i] < dp[ind][j]);
}
int GI(ll x) {
return lower_bound(all(arr), x) - arr.begin();
}
int GIx(int i, ll x) {
return lower_bound(all(ls[i]), x) - ls[i].begin();
}
void build(int v, int tl, int tr) {
t[v] = Mp(m, n);
if (tr - tl == 1) return ;
int mid = (tl + tr) / 2;
build(2 * v + 1, tl, mid); build(2 * v + 2, mid, tr);
}
void set_min(int v, int tl, int tr, int l, int r, pii x) {
l = max(l, tl); r = min(r, tr);
if (l >= tr || r <= tl) return ;
if (l == tl && r == tr) {
t[v] = min(t[v], x);
return ;
}
int mid = (tl + tr) / 2;
set_min(2 * v + 1, tl, mid, l, r, x); set_min(2 * v + 2, mid, tr, l, r, x);
}
pii get_min(int v, int tl, int tr, int i) {
if (i >= tr || i < tl) return Mp(m, n);
if (tr - tl == 1) return t[v];
int mid = (tl + tr) / 2;
return min(t[v], min(get_min(2 * v + 1, tl, mid, i), get_min(2 * v + 2, mid, tr, i)));
}
void init(int Lx, int Nx, vector<ll> T, vector<int> W, int Z, int Mx, vector<int> S) {
L = Lx; n = Nx; m = Mx; X = Z;
for (int i = 0; i < m; i++) R[i] = S[i];
int j = 0;
for (int i = 0; i < n; i++) {
if (W[i] - X <= 0) continue;
A[j] = Mp(T[i], W[i] - X); j++;
}
n = j;
if (n == 0) return ;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0) dp[i][j] = A[j].F;
else {
dp[i][j] = (dp[i - 1][j] + (R[i] - R[i - 1]) * A[j].S);
}
}
if (i - 1 >= 0) {
ind = i - 1;
arr.clear(); arr.resize(n);
iota(all(arr), 0); sort(all(arr), cmp);
ll x1 = -oo, x2 = -oo;
for (int r = 1; r < n; r++) {
int j1 = arr[r - 1], j2 = arr[r];
x2 = max(x2, dp[i][j1]);
if (dp[i - 1][j1] != dp[i - 1][j2]) x1 = x2;
dp[i][j2] = max(dp[i][j2], x1);
}
}
}
arr.clear();
for (int i = 0; i < m; i++) {
ls[i].clear();
for (int j = 0; j < n; j++) {
arr.pb(dp[i][j]);
ls[i].pb(dp[i][j]);
}
sort(all(ls[i])); ls[i].resize(unique(all(ls[i])) - ls[i].begin());
}
sort(all(arr)); arr.resize(unique(all(arr)) - arr.begin());
build(0, 0, len(arr));
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < n; j++) {
if (i + 1 < m) {
int lx = GI(dp[i][j] + 1), rx = GI(dp[i + 1][j] + 1);
set_min(0, 0, len(arr), lx, rx, Mp(i + 1, -GIx(i + 1, dp[i + 1][j])));
}
}
for (int j = 0; j < len(ls[i]); j++) {
pii x = get_min(0, 0, len(arr), GI(ls[i][j])); x.S = -x.S;
if (x.F == m) val[i][j] = ls[i][j];
else val[i][j] = val[x.F][x.S];
}
}
return ;
}
ll arrival_time(ll Y) {
if (n == 0) return (L * X);
ll res = 0;
pii x = get_min(0, 0, len(arr), GI(Y)); x.S = -x.S;
if (x.F == m) res = Y;
else res = val[x.F][x.S];
res += (L * X);
return res;
}
