#include "overtaking.h"
#include<bits/stdc++.h>
using namespace std;
vector<long long> sta;
vector<pair<long long, long long>> bus;
int n, m;
void init(int L, int N, std::vector<long long> T, std::vector<int> W, int X, int M, std::vector<int> S)
{
n = N, m = M;
for(int i = 0; i < M; i++) sta.push_back(S[i]);
for(int i = 0; i < N; i++) bus.push_back({T[i],W[i]});
bus.push_back({-1,X});
}
long long arrival_time(long long Y)
{
int siz = bus.size();
bus[siz-1].first = Y;
long long cur[siz];
for(int i = 0; i < siz; i++) {
cur[i] = bus[i].first;
}
for(int i = 1; i < m; i++) {
priority_queue<pair<pair<long long, long long>,int>, vector<pair<pair<long long,long long>,int>>, greater<pair<pair<long long, long long>,int>>> pq;
pair<long long, long long> mx = {-1,-1};
for(int j = 0; j < siz; j++) {
// cout << cur[j] << ' ' << bus[j].second << ' ' << sta[i] << ' ' << sta[i-1] << ' ' << j << endl;
pq.push({{cur[j],cur[j] + bus[j].second * (sta[i]-sta[i-1])},j});
}
while(!pq.empty()) {
pair<pair<long long, long long>,int> tp = pq.top(); pq.pop();
if(mx.first < tp.first.second) {
mx.first = tp.first.second;
mx.second = tp.first.first;
}
if(mx.second == tp.first.first) {
cur[tp.second] = tp.first.second;
}
else {
cur[tp.second] = mx.first;
}
}
}
return cur[siz-1];
}
/*
6 4 10 4 2
20 10 40 0
5 20 20 30
0 1 3 6
0
50*/
