#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e3;
int n, m, x;
long long timer[MAX][MAX], ans[MAX][MAX];
pair <long long, int> buses[MAX];
vector <int> s;
void init(int L, int N, vector <ll> T, vector <int> W, int X, int M, vector <int> S){
n = 0, m = M, x = X;
s = S;
for (int i = 0; i < N; ++ i) if (W[i] > X)
buses[n ++] = make_pair(T[i], W[i]);
if (n == 0) return;
sort(buses, buses + n);
for (int i = 0; i < n; ++ i)
timer[0][i] = buses[i].first;
for (int i = 1; i < m; ++ i){
for (int j = 0; j < n; ++ j){
buses[j].first += 1ll * (S[i] - S[i - 1]) * buses[j].second;
if (j) buses[j].first = max(buses[j].first, buses[j - 1].first);
}
sort(buses, buses + n);
for (int j = 0; j < n; ++ j)
timer[i][j] = buses[j].first;
}
for (int i = 0; i < n; ++ i)
ans[m - 1][i] = timer[m - 1][i];
for (int i = m - 2; i >= 0; -- i){
ans[i][0] = timer[i][0] + 1ll * (s[m - 1] - s[i]) * x;
for (int j = 1; j < n; ++ j){
if (timer[i][j] == timer[i][j - 1]){
ans[i][j] = ans[i][j - 1];
continue;
}
long long tmp = timer[i][j] + 1ll * (s[m - 1] - s[i]) * x;
if (tmp >= timer[m - 1][j - 1]){
ans[i][j] = tmp;
continue;
}
int low = i + 1, high = m - 1;
while (low < high){
int mid = low + high >> 1;
long long tmp = timer[i][j] + 1ll * (s[mid] - s[i]) * x;
if (tmp <= timer[mid][j - 1]) high = mid;
else low = mid + 1;
}
ans[i][j] = ans[low][j - 1];
}
}
}
long long arrival_time(long long Y){
long long tmp = Y + 1ll * s[m - 1] * x;
if (n == 0 || Y <= timer[0][0])
return tmp;
int low = 1, high = n;
while (low < high){
int mid = low + high >> 1;
if (timer[0][mid] >= Y) high = mid;
else low = mid + 1;
}
int i = low - 1;
if (timer[m - 1][i] <= tmp) return tmp;
low = 1, high = m - 1;
while (low < high){
int mid = low + high >> 1;
long long tmp = Y + 1ll * s[mid] * x;
if (tmp <= timer[mid][i]) high = mid;
else low = mid + 1;
}
return ans[low][i];
}
