#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define pii pair<int,int>
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
#define pb push_back
#define ll long long int
const int N = 2000;
ll dp[N][N], X;
pair<ll, ll> pref[N][N];
int n, m;
vi W, S;
vector<ll> T;
void init(int L, int nn, std::vector<long long> TT, std::vector<int> WW, int XX, int mm, std::vector<int> SS)
{
X = XX;
S = SS;
W = WW;
T = TT;
n = nn;
m = mm;
W.pb(X);
for(int i = 0; i < n; ++i) dp[0][i] = T[i];
for(int i = 1; i < m; ++i){
ll dif = S[i] - S[i - 1];
vector<pair<ll, int>> q;
for(int j = 0; j < n; ++j) q.pb({dp[i-1][j], j});
sort(all(q));
ll last = 0ll, last2 = 0ll;
for(int j = 0; j < n; ++j){
int p = q[j].ss;
dp[i][p] = max(last, dp[i - 1][p] + dif * W[p]);
last2 = max(last2, dp[i][p]);
if(j + 1 < n && q[j+1].ff != q[j].ff) last=max(last,last2);
}
pref[i-1][0] = {q[0].ff, dp[i][q[0].ss]};
for(int j = 1; j < n; ++j){
pref[i-1][j].ff = q[j].ff;
pref[i-1][j].ss = max(
pref[i-1][j-1].ss,
dp[i][q[j].ss]
);
}
}
return;
}
long long arrival_time(long long Y)
{
T.pb(Y);
ll cur = Y;
for(int i = 0; i + 1 < m; ++i){
ll nxt = cur + (S[i + 1] - S[i]) * X;
int pos = lower_bound(pref[i], pref[i] + n, pair<ll, ll>{cur, -1}) - pref[i];
--pos;
if(pos >= 0) nxt = max(nxt, pref[i][pos].ss);
cur = nxt;
}
T.pop_back();
return cur;
}
