#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));
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());
}
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);
}
ll arrival_time(ll Y) {
ll T = Y;
for (int j = 0; j < m - 1; j++) {
pair<pair<ll, ll>, ll> p = {{T, x}, n};
int i = upper_bound(a[j].begin(), a[j].end(), p) - a[j].begin();
p = a[j][i - 1];
T += x * (s[j + 1] - s[j]);
T = max(T, v[j + 1][p.second]);
}
return T;
}
