#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 2000;
const int MAX_M = 2000;
const long long INF = 1e18;
struct bus {
long long t;
int v;
int p;
};
struct answer {
long long l, r, ans;
};
int n, m, x;
bus buses[MAX_N + 1], b[MAX_M][MAX_N + 1];
int s[MAX_M];
vector<long long> times;
vector<answer> ans;
long long query( long long y ) {
for ( int j = 0; j < m - 1; j++ ) {
int l = -1, r = n;
while ( r - l > 1 ) {
int mid = (l + r) / 2;
if ( b[j][mid].t < y )
l = mid;
else
r = mid;
}
y = y + (long long)x * (s[j + 1] - s[j]);
if ( l >= 0 )
y = max( y, b[j + 1][l].t );
}
return y;
}
void init( int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S ) {
n = N;
m = M;
x = X;
for ( int i = 0; i < n; i++ )
buses[i] = { T[i], W[i], i };
for ( int i = 0; i < m; i++ )
s[i] = S[i];
for ( int i = 0; i < n; i++ )
b[0][i] = buses[i];
for( int j = 0; j < m - 1; j++ ) {
sort( b[j], b[j] + n, []( bus a, bus b ) {
if ( a.t == b.t )
return a.v < b.v;
return a.t < b.t;
} );
for ( int i = 0; i < n; i++ )
b[j + 1][i] = b[j][i];
for ( int i = 0; i < n; i++ )
b[j + 1][i].t = b[j][i].t + (long long)b[j][i].v * (s[j + 1] - s[j]);
for ( int i = 1; i < n; i++ )
b[j + 1][i].t = max( b[j + 1][i].t, b[j + 1][i - 1].t );
}
}
long long arrival_time( long long y ) {
return query( y );
}
