#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define NAME ""
#define ll long long
#define pii pair < int , int >
#define pll pair < ll , ll >
#define fi first
#define se second
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i ++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i --)
#define REP(i, n) for (int i = 0, _n = (n); i < _n; i ++)
#define bit(x, i) (((x) >> (i)) & 1ll)
#define mask(x) (1ll << (x))
#define mem(f, x) memset(f, x, sizeof(f))
#define sz(x) (int32_t) (x.size())
const int nmax = 1000;
int n, m, x;
ll f[nmax + 4][nmax + 4];
pll g[nmax + 4][nmax + 4];
vector < int > s;
void init(int l, int _n, std::vector<long long> t, std::vector<int> w, int _x, int _m, std::vector<int> _s) {
n = _n;
m = _m;
x = _x;
s = _s;
REP(i, n) {
f[i][0] = t[i];
}
vector < int > id(n, 0);
iota(id.begin(), id.end(), 0);
FOR(j, 1, m - 1) {
sort(id.begin(), id.end(), [&] (const int &x, const int &y) {
return ((f[x][j - 1] < f[y][j - 1]) || (f[x][j - 1] == f[y][j - 1] && w[x] < w[y]));
});
REP(x, n) {
int i = id[x];
f[i][j] = f[i][j - 1] + 1ll * (s[j] - s[j - 1]) * w[i];
if (x > 0) {
f[i][j] = max(f[i][j], f[id[x - 1]][j]);
}
}
}
FOR(j, 0, m - 2) {
REP(i, n) {
g[j][i] = {f[i][j], f[i][j + 1]};
}
sort(g[j], g[j] + n);
FOR(i, 1, n - 1) {
g[j][i].se = max(g[j][i].se, g[j][i - 1].se);
}
// REP(i, n) {
// cout << g[j][i].se << " ";
// }
// cout << "\n";
}
}
long long arrival_time(long long y) {
f[n][0] = y;
FOR(j, 0, m - 2) {
f[n][j + 1] = f[n][j] + 1ll * (s[j + 1] - s[j]) * x;
int k = lower_bound(g[j], g[j] + n, pll{f[n][j], 0}) - g[j] - 1;
if (k >= 0) {
f[n][j + 1] = max(f[n][j + 1], g[j][k].se);
}
}
return f[n][m - 1];
}
