#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;
};
int n, m, x;
bus buses[MAX_M][MAX_N];
long long timeByBus[MAX_M][MAX_N];
long long arrivalTime[MAX_M][MAX_N];
int stations[MAX_M];
int countAhead(int s, long long t) {
int l = -1, r = n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (buses[s][mid].t < t)
l = mid;
else
r = mid;
}
return r;
}
long long getArrivalTime(int s, long long t) {
int l = s, r = m;
while (r - l > 1) {
int mid = (l + r) / 2;
long long d = stations[mid] - stations[s];
long long timeMid = t + (long long)d * x;
if (countAhead(mid, timeMid) == countAhead(s, t))
l = mid;
else
r = mid;
}
if (r == m)
return t + (long long)x * (stations[m - 1] - stations[s]);
// printf("%d %lld %d\n", s, t, buses[r][countAhead(s, t) - 1].p);
return arrivalTime[r][buses[r][countAhead(s, t) - 1].p];
}
void init(int L, int N, vector<long long> T, vector<int> W, int X, int M, vector<int> S) {
m = M;
x = X;
n = 0;
for (int i = 0; i < N; i++) {
if (W[i] > x)
buses[0][n++] = {T[i], W[i], n - 1};
}
for (int i = 0; i < m; i++)
stations[i] = S[i];
for (int j = 0; j < m - 1; j++) {
sort(buses[j], buses[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++)
buses[j + 1][i] = buses[j][i];
for (int i = 0; i < n; i++)
buses[j + 1][i].t = buses[j][i].t + (long long)buses[j][i].v * (stations[j + 1] - stations[j]);
for (int i = 1; i < n; i++)
buses[j + 1][i].t = max(buses[j + 1][i].t, buses[j + 1][i - 1].t);
// for (int i = 0; i < n; i++)
// printf("%lld ", buses[j + 1][i].t);
// printf("\n");
}
for (int j = 0; j < m; j++) {
for (int i = 0; i < n; i++)
timeByBus[j][buses[j][i].p] = buses[j][i].t;
buses[j][n].t = INF;
}
for (int i = 0; i < n; i++)
arrivalTime[m - 1][buses[m - 1][i].p] = buses[m - 1][i].t;
for (int j = m - 2; j >= 0; j--) {
for (int i = 0; i < n; i++)
arrivalTime[j][buses[j][i].p] = getArrivalTime(j, buses[j][i].t);
}
// for (int s = m - 1; s >= 0; s--) {
// for (int i = 0; i < n; i++)
// printf("%lld ", arrivalTime[s][buses[s][i].p]);
// printf("\n");
// }
}
long long arrival_time(long long y) {
return getArrivalTime(0, y);
}
