#include<bits/stdc++.h>
#include "overtaking.h"
using namespace std;
using ll = long long;
vector<long long> tim;
vector<long long> speed;
int n , m ;
vector<pair<long long , long long>> dp[2001]; // ekhane hoitop swize thik koro
vector<long long> pref[2001];
long long goti;
vector<long long> terms;
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S)
{
tim.clear();
speed.clear();
goti = (ll)X;
terms.clear();
for( int z = 0; z < M; z++ ) {
terms.push_back((ll)S[z]);
}
for( int z = 0; z < N; z++ ) {
if( W[z] > X ) {
tim.push_back(T[z]);
speed.push_back((ll)W[z]);
}
}
n = tim.size();
m = M;
for( int z = 0; z <= m; z++ ) {
dp[z].clear();
pref[z].clear();
dp[z].push_back({0 , 0});
pref[z].push_back(0);
}
for( int z = 0; z < n; z++ ) {
dp[0].push_back({tim[z] , speed[z]});
}
sort(dp[0].begin() , dp[0].end() );
for( int z = 1; z < m; z++ ) {
long long boro = 0;
int here = 0;
for( int y = 1; y <= n; y++ ) {
ll uttor = ((ll)S[z] - (ll)S[z - 1]) * (dp[z - 1][y].second);
uttor += dp[z - 1][y].first;
if( dp[z - 1][y].first != dp[z - 1][y - 1].first ) {
for( int x = here + 1; x < y; x++ ) {
boro = max( boro , dp[z][x].first );
}
here = y - 1;
}
uttor = max( uttor , boro );
dp[z].push_back( { uttor , dp[z - 1][y].second } );
pref[z - 1].push_back(uttor);
}
sort( dp[z].begin() , dp[z].end() );
}
// cerr << "done" << "\n";
}
long long arrival_time(long long Y)
{
long long cur = Y;
ll uttor = 0;
for( int z = 0; z < m - 1; z++ ) {
int l = 0;
int r = n;
while( l != r ) {
int mid = (l + r + 1) / 2;
if( dp[z][mid].first < cur ) {
l = mid;
}
else r = mid - 1;
}
uttor = cur + ((terms[z + 1] - terms[z]) * goti);
cur = max( uttor , pref[z][r] );
}
return cur;
}
