#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<pair<ll, ll>> car;
int n;
vector<vector<ll>> arr;
vector<ll> s;
int m;
ll x;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
for(int i = 0; i < N; ++i) {
if (X < W[i]) {
car.push_back({T[i], W[i]});
}
}
x = X;
n = car.size();
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
// std::cout<<std::endl;
m = M;
s.push_back(S[0]);
for (int i = 1; i < M; ++i) {
for(int j = 0; j < n; ++j) {
car[j].first += car[j].second * (S[i] - S[i - 1]);
}
for (int j = 1; j < n; ++j) {
car[j].first = max(car[j].first, car[j - 1].first);
}
sort(car.begin(), car.end());
arr.push_back(vector<ll>{});
for (int j = 0; j < n; ++j) {
arr.back().push_back(car[j].first);
// std::cout<<car[j].first<<" ";
}
// std::cout<<std::endl;
s.push_back(S[i]);
}
return;
}
long long arrival_time(long long Y)
{
for (int i = 1; i < m; ++i) {
int pos = upper_bound(arr[i - 1].begin(), arr[i - 1].end(), Y - 1) - arr[i - 1].begin() - 1;
if (pos == -1) {
Y = Y + x * (s[i] - s[i - 1]);
} else {
Y = max(Y + x * (s[i] - s[i - 1]), arr[i][pos]);
}
}
return Y;
}
