#include "overtaking.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll tn;
ll l, n, m;
vector<int> stations;
struct Line{
ll a, b, id; Line( ll a = 0, ll b = 0, ll id = 0 ) : a(a), b(b), id(id) {}
bool operator < ( Line l ){
if( b == l.b ) return a > l.a;
return b > l.b;
}
ll calc( ll x ){ return a*x + b; }
};
vector<Line> bus;
void init(int L, int N, vector<ll> T, vector<int> W, int X, int M, vector<int> S)
{
tn = X;
l = L;
n = N;
m = M;
for( int i = 0; i < n; i++ ) bus.push_back(Line( W[i], T[i], i ));
stations = S;
}
ll arrival_time(ll y){
vector<vector<int>> adj(n + 1);
vector<int> t(n + 1), marc(n + 1);
vector<Line> lines;
for( auto x : bus ) lines.push_back(x);
lines.push_back(Line(tn, y, n));
function<void(int, int)> dfs = [&]( int cur, ll val ){
t[cur] = val;
marc[cur] = true;
for( int viz : adj[cur] ) dfs( viz, val );
};
for( int pos = 1; pos < (int)stations.size(); pos++ ){
fill( marc.begin(), marc.end(), 0);
sort( lines.begin(), lines.end() );
adj.clear();
adj.resize(n + 1);
stack<pair<ll, int>> pilha;
ll delta = stations[pos] - stations[pos - 1];
for( auto x : lines ){
t[x.id] = x.calc(delta);
while( !pilha.empty() && pilha.top().first <= t[x.id] ){
adj[x.id].push_back(pilha.top().second );
pilha.pop();
}
pilha.push({ t[x.id], x.id });
}
reverse( lines.begin(), lines.end() );
for( auto x : lines ) if( !marc[x.id] ) dfs( x.id, t[x.id] );
lines.clear();
for( auto x : bus ) lines.push_back(Line(x.a, t[x.id], x.id));
lines.push_back(Line(tn, t[n], n ));
}
return t[n];
}
