#include "overtaking.h"
#include <bits/stdc++.h>
#define forsn(i, s, n) for (int i = int(s); i < int(n); i++)
#define forn(i, n) forsn(i, 0, n)
#define dforsn(i, s, n) for (int i = int(n) - 1; i >= int(s); i--)
#define dforn(i, n) dforsn(i, 0, n)
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define pb push_back
#define eb emplace_back
#define fst first
#define snd second
using namespace std;
using vi = vector<int>;
using ii = pair<int, int>;
using ll = long long;
using vll = vector<ll>;
using pll = pair<ll, ll>;
const int MAX_N = 1005;
ll e[MAX_N][MAX_N], dp[MAX_N][MAX_N];
ll s[MAX_N], w[MAX_N], t[MAX_N], x;
int n, m;
void init(int /*L*/, int N, vll T, vi W, int X, int M, vi S) {
n = M, m = N, x = X;
forn(i, n) s[i] = S[i];
{
int j = 0;
forn(i, m) if (W[i] > X) {
w[j] = W[i], t[j] = T[i];
j++;
}
m = j;
}
vector<pll> v(m);
forn(i, m) v[i] = {t[i], w[i]};
forn(i, n) {
sort(all(v));
forn(j, m) {
if (i > 0) v[j].fst += v[j].snd * (s[i] - s[i - 1]);
if (j > 0) v[j].fst = max(v[j].fst, v[j - 1].fst);
e[i][j] = v[j].fst;
}
}
forn(j, m) dp[n - 1][j] = e[n - 1][j];
dforn(i, n - 1) {
dp[i][0] = e[i][0] + (s[n - 1] - s[i]) * x;
forsn(j, 1, m) {
int lo = i, hi = n;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (e[mid][j - 1] >= e[i][j] + (s[mid] - s[i]) * x) {
hi = mid;
} else {
lo = mid;
}
}
if (hi == n) dp[i][j] = e[i][j] + (s[n - 1] - s[i]) * x;
else dp[i][j] = dp[hi][j - 1];
}
forsn(j, 1, m) if (e[i][j] == e[i][j - 1]) dp[i][j] = min(dp[i][j], dp[i][j - 1]);
dforn(j, m - 1) if (e[i][j] == e[i][j + 1]) dp[i][j] = min(dp[i][j], dp[i][j + 1]);
}
}
ll arrival_time(ll Y) {
int lo = -1, hi = m;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (e[0][mid] < Y) lo = mid;
else hi = mid;
}
if (lo == -1) return Y + s[n - 1] * x;
int curr = lo;
lo = -1, hi = n;
while (hi - lo > 1) {
int mid = (lo + hi) / 2;
if (e[mid][curr] >= Y + s[mid] * x) {
hi = mid;
} else {
lo = mid;
}
}
if (hi == n) return Y + s[n - 1] * x;
return dp[hi][curr];
}
