#include "overtaking.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
typedef long long ll;
typedef long double ld;
#define endl "\n"
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
#define inf (ll)1e15
#define db(x) cout<<#x<<" : "<<x<<endl;
#define PRESICION(x) cout.setf(ios::fixed,ios::floatfield); cout.precision(x);
using namespace std;
using namespace __gnu_pbds;
ll dx[]={1, -1, 0, 0};
ll dy[]={0, 0, 1, -1};
inline ll sm(ll a, ll b){
return ((a%mod)+(b%mod))%mod;
}
inline ll ml(ll a, ll b){
return ((a%mod)*(b%mod))%mod;
}
inline ll rs(ll a, ll b){
return ((a%mod)-(b%mod)+mod)%mod;
}
ll bpow(ll a , ll b) {
if (b==0)return 1;
if (b%2!=0)return ((bpow(a, b-1)%mod)*(a%mod))%mod;
ll r=bpow (a ,b/ 2) ;
return ((r%mod)*(r%mod))%mod;
}
vector<vector<ll>> res;
ll x, m, l, n;
vector<ll> t, w, s1;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S){
n=N;
m=M;
vector<vector<ll>>().swap(res);
vector<ll>().swap(w);
vector<ll>().swap(s1);
res.resize(N+1, vector<ll>(M));
w.resize(N+1);
s1.resize(N+1);
for(int i=0; i<N; i++)w[i]=W[i];
for(int i=0; i<M; i++)s1[i]=S[i];
w[N]=X;
for(int i=0; i<N; i++)res[i][0]=T[i];
return;
}
long long arrival_time(long long Y){
res[n][0]=Y;
ll cnt=0;
set<tuple<ll, ll, ll>> s;
for(int i=0; i<=n; i++){s.insert({res[i][0], w[i], i});}
for(int i=1; i<m; i++){
ll o=-1;
for(auto& [x, o1, y]: s){
o=max(o, x+(w[y]*(s1[i]-s1[i-1])));
//cout<<i<<" "<<x<<" "<<y<<" "<<w[y]<<" "<<x+(w[y]*(s1[i]-s1[i-1]))<<endl;
res[y][i]=o;
}
set<tuple<ll, ll, ll>>().swap(s);
for(int j=0; j<=n; j++)s.insert({res[j][i], w[j], j});
}
/*for(int j=0; j<m; j++){
cout<<j<<endl;
for(int i=0; i<=n; i++){
cout<<res[i][j]<<" ";
}
cout<<endl;
}*/
return res[n][m-1];
}
