#include "overtaking.h"
#include <algorithm>
using namespace std;
typedef long long llong;
const int MAXN = 1e3 + 10;
const int MAXM = 1e3 + 10;
const int MAXQ = 1e6 + 10;
struct Bus
{
llong speed, start;
int idx;
Bus(){};
Bus(llong speed, llong start, int idx)
{
this->speed = speed;
this->start = start;
this->idx = idx;
}
friend bool operator<(const Bus& b1, const Bus& b2)
{
if(b1.start != b2.start)
return b1.start < b2.start;
return b1.speed < b2.speed;
}
};
int n, m, q;
int l, x;
Bus b[MAXM][MAXN];
int pos[MAXM];
pair < llong, llong > travel[MAXM][MAXN];
void init(int L, int N, vector < llong > T, vector < int > W, int X, int M, vector < int > S)
{
l = L;
n = N;
x = X;
m = M;
for(int i = 0; i < n; i++)
{
b[0][i] = Bus(W[i], T[i], i);
}
for(int i = 0; i < m; i++)
{
pos[i] = S[i];
}
for(int i = 0; i < m - 1; i++)
{
sort(b[i], b[i] + n);
llong maxexp = 0;
for(int j = 0; j < n; j++)
{
llong exp = b[i][j].start + b[i][j].speed * 1LL * (pos[i + 1] - pos[i]);
maxexp = max(maxexp, exp);
travel[i][j] = {b[i][j].start, maxexp};
b[i + 1][j].start = maxexp;
}
}
}
llong arrival_time(llong Y)
{
llong cur = Y;
for(int i = 0; i < m - 1; i++)
{
llong exp = cur + 1LL * x * (pos[i + 1] - pos[i]);
pair < llong, llong > p = {cur, 0};
int col = lower_bound(travel[i], travel[i] + n, p) - travel[i] - 1;
if(col == -1)
cur = exp;
else
cur = max(exp, travel[i][col].second);
}
return cur;
}
