#include "overtaking.h"
#include "bits/stdc++.h"
using namespace std;
#define rep(i,a,b) for(int i = a;i < b;i++)
#define trav(nx, v) for(auto &nx: v)
#define sz(v) (int) v.size()
#define all(v) begin(v), end(v)
#define pb push_back
#define fi first
#define se second
int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
typedef __int128 LL;


namespace Solver{
	struct Bus {
		LL pointInTime, speed, idx;
		bool operator <(const Bus &other) const {
			if(pointInTime != other.pointInTime) return pointInTime < other.pointInTime;
			if(speed != other.speed) return speed < other.speed;
			return idx < other.idx;
			//~ return tie(pointInTime, idx, other) < tie(other.pointInTime, idx, other.speed);
			
		}
	};
	LL n, roadLength;
	vector <Bus> busList;
	LL m;
	LL sortingStation[1005];
	Bus reserved;
};


using namespace Solver;

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;
    roadLength = L;
	m = M;
	for(int i = 0;i < m;i++) sortingStation[i] = S[i];
	rep(i,0,n){
		if(W[i] <= X) continue;
		Bus currentBus = {T[i], W[i], sz(busList)};
		busList.pb(currentBus);
	}
	n = sz(busList);
	reserved.speed = X;
	reserved.idx = n;
    sort(all(busList));
   
    return;
}

long long arrival_time(long long Y){
	vector <Bus> busses = busList;
	reserved.pointInTime = Y;
	busses.pb(reserved);
	sort(all(busses));
	rep(i,1,m){
		// Buang bus yang ga penting
		while(!busses.empty() && busses.back().idx != n) {
			//~ cout << cur.pointInTime << " " << cur.speed << " " << cur.idx << endl;
			busses.pop_back();
		}
		Bus curReserved = busses.back();
		while(!busses.empty() && busses.back().pointInTime == curReserved.pointInTime) busses.pop_back();
		busses.pb(curReserved);
		int curSize = sz(busses);
		// Compute expected arrival
		LL distance = sortingStation[i] - sortingStation[i - 1];
		LL maksi = LLONG_MIN;
		//~ cout << "At station " << i << ", cursize " << curSize << " : "  << endl;
		//~ trav(cur, busses) cout << cur.pointInTime << " " << cur.speed << endl;
		for(int j = 0;j < curSize;j++){
			busses[j].pointInTime += distance * busses[j].speed;
			maksi = max(maksi, busses[j].pointInTime);
			busses[j].pointInTime = maksi;
		}
		//~ cout << "At station " << i << ", cursize " << curSize << " : "  << endl;
		//~ trav(cur, busses) cout << cur.pointInTime << " " << cur.speed << " " << cur.idx << endl;
		sort(all(busList));
	}
	rep(i,0,sz(busses)){
		if(busses[i].idx == n) return busses[i].pointInTime;
	}
    return 0;
}