#include <bits/stdc++.h>
#include "overtaking.h"
using namespace std;
using ll = long long;
const int N = 1009;
ll f[N][N];
ll L, n, x, m, q;
vector < ll > t(N), w(N), s(N);
vector < vector < ll > > e(N, vector < ll > (N));
void init(int l_, int n_, vector < ll > t_, vector < int > w_, int x_, int m_, vector < int > s_) {
L = l_, n = n_, m = m_, x = x_;
for (int i = 0; i < m; i++) s[i] = s_[i];
for (int i = 0; i < n; i++) t[i] = t_[i], w[i] = w_[i];
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++) {
if (!j) e[j][i] = t[i];
else e[j][i] = e[j - 1][i] + w[i] * (s[j] - s[j - 1]);
}
if (j) {
for (int i = 0; i < n; i++) {
for (int k = 0; k < n; k++) if (e[j - 1][k] < e[j - 1][i]) e[j][i] = max(e[j][i], e[j][k]);
}
}
}
for (int j = m - 1; j >= 0; j--) {
for (int i = 0; i < n; i++) {
if (j == m - 1) f[j][i] = e[j][i];
else {
int mnl = (int)1e9, opt = -1;
for (int k = 0; k < n; k++) {
if (e[j][k] >= e[j][i]) continue;
int l = j + 1, r = m - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (e[j][k] + w[k] * (s[mid] - s[j]) >= e[j][i] + x * (s[mid] - s[j])) r = mid;
else l = mid + 1;
}
if (e[l][k] >= e[j][i] + x * (s[l] - s[j]) && (l < mnl ||
(l == mnl && e[l][k] > e[l][opt]))) {
mnl = l, opt = k;
}
}
if (mnl < (int)1e9) f[j][i] = f[mnl][opt];
else f[j][i] = e[j][i] + x * (L - s[j]);
}
}
}
}
ll arrival_time(ll y) {
int mnl = (int)1e9, opt = -1, j = 0;
for (int k = 0; k < n; k++) {
if (e[j][k] >= y) continue;
int l = j + 1, r = m - 1;
while (l < r) {
int mid = (l + r) >> 1;
if (t[k] + w[k] * s[mid] >= y + x * (s[mid] - s[j])) r = mid;
else l = mid + 1;
}
if (t[k] + w[k] * s[l] >= y + x * (s[l] - s[j]) && (l < mnl ||
(l == mnl && e[l][k] > e[l][opt]))) {
mnl = l, opt = k;
}
}
if (mnl < (int)1e9) return f[mnl][opt];
return x * L + y;
}
