#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Bus {
ll t, w;
int id;
};
bool cmp(const Bus &a, const Bus &b) {
if (a.t == b.t) return a.w < b.w;
return a.t < b.t;
}
int N, M;
vector<int> stations;
vector<Bus> buses, buses_init;
vector<ll> arrTimes_station[1005];
ll dist(int i) {
return stations[i] - stations[i - 1];
}
ll compute(ll t, ll w, int j) {
return t + dist(j) * w;
}
void init(int Lp, int Np, vector<ll> Tp, vector<int> Wp, int Xp, int Mp, vector<int> Sp) {
buses.clear();
stations = Sp;
for (int i = 0; i < Np; i++) {
if (Wp[i] >= Xp) buses.push_back({Tp[i], Wp[i], i});
}
buses.push_back({0, (ll)Xp, Np});
N = (int)buses.size();
M = Mp;
buses_init = buses;
for (int j = 1; j < M; j++) {
sort(buses.begin(), buses.end(), cmp);
ll curMax = 0;
arrTimes_station[j].clear();
arrTimes_station[j].reserve(N);
for (int i = 0; i < N; i++) {
ll expected = compute(buses[i].t, buses[i].w, j);
buses[i].t = max(expected, curMax);
curMax = max(curMax, buses[i].t);
arrTimes_station[j].push_back(buses[i].t);
}
}
}
ll arrival_time(ll Y) {
buses = buses_init;
ll arrival = Y, pace = 0;
for (auto &b : buses) {
if (b.id == N - 1) {
b.t = Y;
pace = b.w;
break;
}
}
for (int j = 1; j < M; j++) {
auto &arr = arrTimes_station[j];
int pos = (int)(upper_bound(arr.begin(), arr.end(), arrival) - arr.begin());
ll block = (pos == 0) ? 0 : arr[pos - 1];
arrival = max(arrival + dist(j) * pace, block);
for (auto &b : buses) {
if (b.id == N - 1) {
b.t = arrival;
break;
}
}
}
for (auto &b : buses)
if (b.id == N - 1) return b.t;
return -1;
}
