#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
vector<ll> ex;
ll x, n, m, l;
vector<ll> w, t, s;
void init(int _l, int _n, vector<ll> _t, vi _w, int _x, int _m, vi _s) {
n = _n; m = _m; x = _x; l = _l; t = _t;
w = vector<ll>(_w.begin(), _w.end());
s = vector<ll>(_s.begin(), _s.end());
w.push_back(x);
t.push_back(0);
ex.resize(m);
for (int i = 0; i < m; i++) {
ex[i] = s[i] * w[0] + t[0];
}
}
ll arrival_time(ll y) {
t[n] = y;
vector<vector<ll>> dp(m, vector<ll>(n + 1));
dp[0] = t;
vector<pair<ll, int>> srt(n + 1);
for (int i = 0; i <= n; i++) {
srt[i] = {dp[0][i], i};
}
sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
if (_i.first == _j.first) return w[_i.second] < w[_j.second];
return _i.first < _j.first;
});
for (int j = 1; j < m; j++) {
ll ma = 0;
for (auto [tm, i]: srt) {
ma = max(ma, dp[j - 1][i] + w[i] * (s[j] - s[j - 1]));
dp[j][i] = ma;
}
for (int i = 0; i <= n; i++) {
srt[i] = {dp[j][i], i};
}
sort(srt.begin(), srt.end(), [&](auto _i, auto _j){
if (_i.first == _j.first) return w[_i.second] < w[_j.second];
return _i.first < _j.first;
});
}
return dp[m - 1][n];
}
