/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#include"overtaking.h"
ll n,m,x;
vector<ll>t,w,s;
void init(int L,int N,vector<ll>T,vector<int>W,int X,int M,vector<int>S){
n=N;m=M;t=T;x=X;
for(auto&i:W)w.push_back(i);
for(auto&i:S)s.push_back(i);
}
ll arrival_time(ll y){
n++;
t.push_back(y);
w.push_back(x);
vector<int>p(n);
iota(p.begin(),p.end(),0);
vector<ll>v=t;
for(int i=1;i<m;i++){
sort(p.begin(),p.end(),[&](int l,int r){return v[l]<v[r];});
vector<ll>nv(n);
ll mx=0;
for(int j=0;j<n;j++){
int k=j;
while(k<n&&v[p[k]]==v[p[j]])k++;k--;
for(int l=j;l<=k;l++)nv[p[l]]=max(mx,v[p[l]]+(s[i]-s[i-1])*w[p[l]]);
for(int l=j;l<=k;l++)mx=max(mx,nv[p[l]]);
j=k;
}
v=nv;
}
t.pop_back();
w.pop_back();
n--;
return v[n];
}
