#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll l, n, x, m;
vector<ll> t;
vector<ll> w(2e3, 0);
vector<ll> s(2e3, 0);
vector<vector<pair<pair<ll, ll>, ll> > > a(2e3);
vector<vector<ll> > v(2e3, vector<ll>(2e3, 0));
vector<vector<pair<ll, ll> > > u(2e3);
vector<vector<ll> > dp(2e3, vector<ll>(2e3, 0));
void solve(int j) {
for (auto p: a[j - 1]) {
ll T = p.first.first + p.first.second * (s[j] - s[j - 1]);
a[j].push_back({{T, p.first.second}, p.second});
}
for (int i = 1; i <= n; i++) {
a[j][i].first.first = max(a[j][i].first.first, a[j][i - 1].first.first);
v[j][a[j][i].second] = a[j][i].first.first;
}
sort(a[j].begin(), a[j].end());
}
ll calc(int j, ll t) {
pair<ll, ll> p = {t, -1};
int lb = lower_bound(u[j].begin(), u[j].end(), p) - u[j].begin();
if (!lb) return t + x * (s[m - 1] - s[j]);
int i = u[j][lb - 1].second, l = j, r = m, k;
while (r - l > 1) {
k = (l + r) / 2;
(v[k][i] < t + x * (s[k] - s[j]) ? l = k : r = k);
}
if (r == m) return t + x * (s[m - 1] - s[j]);
return dp[r][i];
}
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S) {
l = L;
n = N;
x = X;
m = M;
t = T;
for (int i = 0; i < n; i++) w[i] = W[i];
for (int j = 0; j < m; j++) s[j] = S[j];
for (int i = 0; i < n; i++) a[0].push_back({{t[i], w[i]}, ll(i)});
a[0].push_back({{0, 0}, n + 1});
a[0].push_back({{4e18, 0}, n + 1});
sort(a[0].begin(), a[0].end());
for (int j = 1; j < m; j++) solve(j);
for (int j = 0; j < m; j++) {
for (int i = 1; i <= n; i++) {
if (a[j][i].first.second <= x) continue;
u[j].push_back({a[j][i].first.first, a[j][i].second});
}
}
for (int i = 0; i < n; i++) {
dp[m - 1][i] = v[m - 1][i];
}
for (int j = m - 2; j >= 0; j--) {
for (int i = 0; i < n; i++) {
dp[j][i] = calc(j, v[j][i]);
}
}
}
ll arrival_time(ll Y) {
return calc(0, Y);
}
