#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
using lli=long long;
#define pb push_back
lli Nx;
lli Ti;
lli Wi;
lli Xi;
lli Lx;
lli Mx;
vector<int> st;
vector<pair<lli,lli>> val;
vector<lli> Tx;
vector<int> Wx;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
Nx=N;
Mx=M;
if(N==1){
Ti=T[0];
Wi=W[0];
Xi=X;
st=S;
return;
}
if(M==2){
Lx=L;
Xi=X;
for(int i=0; i<N; ++i){
val.pb({T[i], W[i]});
}
sort(val.begin(), val.end());
return;
}
Xi=X;
st=S;
Tx=T;
Wx=W;
}
long long arrival_time(long long Y)
{
if(Nx==1){
lli M=st.size();
vector<lli> t (M);
vector<lli> yi (M);
t[0]=Ti;
yi[0]=Y;
for(lli i=1; i<M; ++i){
t[i]=t[i-1]+(st[i]-st[i-1])*Wi;
yi[i]=yi[i-1]+(st[i]-st[i-1])*Xi;
if(t[i-1]>yi[i-1]){
if(t[i]<yi[i]){
t[i]=yi[i];
}
}
else if(t[i-1]<yi[i-1]){
if(t[i]>yi[i]){
yi[i]=t[i];
}
}
}
return yi[M-1];
}
if(Mx==2){
lli valmax=Y+Lx*Xi;
for(lli i=0; i<Nx; ++i){
if(val[i].first<Y){
valmax=max(valmax, val[i].first+Lx*val[i].second);
}
}
return valmax;
}
vector<lli> values =Tx;
values.pb(Y);
priority_queue<pair<pair<lli,lli>, lli>, vector<pair<pair<lli,lli>, lli>>, greater<pair<pair<lli,lli>, lli>>> pq;
for(lli i=0; i<Nx; ++i){
pq.push({{values[i], Wx[i]}, i});
}
pq.push({{Y, Xi}, Nx});
for(lli i=1; i<st.size(); ++i){
lli maxi=0;
while(!pq.empty()){
lli a=pq.top().first.first;
lli b=pq.top().first.second;
lli c=pq.top().second;
pq.pop();
maxi=max(maxi, a+b*(st[i]-st[i-1]));
values[c]=maxi;
}
for(lli i=0; i<Nx; ++i){
pq.push({{values[i], Wx[i]}, i});
}
pq.push({{values[Nx], Xi}, Nx});
}
return values[Nx];
}
