#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
int L,N,X,M;
vector<long long> T,W,S;
vector<vector<pair<long long,long long>>> DP;
vector<vector<pair<long long,long long>>> DPprev;
}
void gen() {
DP = vector<vector<pair<long long,long long>>>(M);
DPprev = vector<vector<pair<long long,long long>>>(M);
for(int i=0;i<N;i++)DP[0].emplace_back(T[i],W[i]);
sort(DP[0].begin(),DP[0].end());
for(int i=1;i<M;i++) {
for(int j=0;j<N;j++) {
long long e = DP[i-1][j].first+DP[i-1][j].second*(S[i]-S[i-1]);
int trans = -1;
auto iter = lower_bound(DP[i-1].begin(),DP[i-1].end(),make_pair(DP[i-1][j].first,0ll))-DP[i-1].begin();
trans = iter-1;
if(trans!=-1)e=max(e,DP[i][trans].first);
DP[i].emplace_back(e,DP[i-1][j].second);
DPprev[i].emplace_back(e,DP[i-1][j].second);
}
sort(DP[i].begin(),DP[i].end());
}
}
void init(int L,int N,vector<long long> T,vector<int> W,int X,int M,vector<int> S){
W.emplace_back(X);
::L = L;
::N = N;
::T = T;
for(int&i:W)::W.emplace_back(i);
::X = X;
::M = M;
for(int&i:S)::S.emplace_back(i);
gen();
}
long long arrival_time(long long Y){
long long e = Y;
for(int i=1;i<M;i++) {
auto iter = lower_bound(DP[i-1].begin(),DP[i-1].end(),make_pair(e,0ll))-DP[i-1].begin();
e+=X*(S[i]-S[i-1]);
if(iter!=0)e = max(e,DPprev[i][iter-1].first);
}
return e;
}
