#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];
long long getArrivalTime(int s, long long t) {
int l = s, r = m;
while (r - l > 1) {
int mid = (l + r) / 2;
bool ok = false;
for (int i = 0; i < n; i++) {
int b = buses[s][i].p;
if (timeByBus[s][b] < t && timeByBus[mid][b] >= t + (long long)x * (stations[mid] - stations[s]))
ok = true;
}
if (ok)
r = mid;
else
l = mid;
}
// printf("ARRIVAL %d %lld %d %d\n", s, t, r, x);
if (r == m)
return t + (long long)x * (stations[m - 1] - stations[s]);
int bus = 0;
long long maxx = 0;
for (int i = 0; i < n; i++) {
int b = buses[s][i].p;
if (timeByBus[s][b] < t) {
if (timeByBus[r][b] > maxx) {
maxx = timeByBus[r][b];
bus = b;
}
}
}
// printf("BUS %d %lld\n", bus, arrivalTime[r][bus]);
return arrivalTime[r][bus];
}
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[0][i] = {T[i], W[i], i};
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][i]);
// printf("\n");
// }
}
long long arrival_time(long long y) {
return getArrivalTime(0, y);
}
