#include "overtaking.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 1000;
const int MAX_M = 1000;
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<answer> ans;
long long ymax, ymin;
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( signed L, signed N, vector<long long> T, vector<signed> W, signed X, signed M, vector<signed> 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];
ymax = 0;
ymin = INF;
for ( int i = 0; i < n; i++ ) {
if ( b[0][i].v > x ) {
ymax = max( ymax, b[0][i].t - (long long)x * s[0] );
ymin = min( ymin, b[0][i].t - (long long)x * s[0] );
}
}
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 );
}
for ( int j = 0; j < m; j++ ) {
for ( int i = 0; i < n; i++ ) {
if ( b[j][i].v > x ) {
ymax = max( ymax, b[j][i].t - (long long)x * s[j] );
ymin = min( ymin, b[j][i].t - (long long)x * s[j] );
}
}
}
ymin = max( ymin, -1LL );
// printf( "%lld %lld\n", ymin, ymax );
long long y = ymin + 1;
int cons = 0;
while ( y < ymax ) {
long long l = y, r = ymax;
while ( r - l > 1 ) {
long long mid = (l + r) / 2;
if ( query( mid ) == query( y ) )
l = mid;
else
r = mid;
}
//printf( "%lld %lld %lld\n", y, l, query( y ) );
ans.push_back( { y, l, query( y ) } );
y = r;
}
//printf( "%lld %lld\n", ymin, ymax );
}
long long arrival_time( long long y ) {
if ( y >= ymax || y <= ymin )
return y + (long long)x * s[m - 1];
long long l = 0, r = ans.size();
while ( r - l > 1 ) {
long long mid = (l + r) / 2;
if ( ans[mid].l <= y )
l = mid;
else
r = mid;
}
return ans[l].ans;
}
