#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 long long LL;
typedef pair<LL, LL> PLL;

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;
	vector <Bus> precompute[1005];
	vector <Bus> sortedPrecompute[1005];
	vector <PLL> precomputeJawaban;
    set <PLL> cari;
};


using namespace Solver;


void initDP(){
	
	vector <Bus> busses = busList;
	sort(all(busses));
	sortedPrecompute[0] = busses;
	int curSize = sz(busses);
	rep(i,1,m){
		LL distance = sortingStation[i] - sortingStation[i - 1];
		LL maksi = LLONG_MIN;
		for(int j = 0;j < curSize;j++){
			busses[j].pointInTime += distance * busses[j].speed;
			maksi = max(maksi, busses[j].pointInTime);
			busses[j].pointInTime = maksi;
		}
		precompute[i] = busses;
		sort(all(busses));
		sortedPrecompute[i] = busses;
	}
}



long long arrival_pre(long long Y){
	Bus curReserved = reserved;
	curReserved.pointInTime = Y;
	auto position = upper_bound(all(sortedPrecompute[0]), curReserved) 
						- begin(sortedPrecompute[0]);
	//~ cout << "querying " << Y << " " << position << endl;
	rep(i,1,m){
		//~ cout << position << endl;
		LL distance = sortingStation[i] - sortingStation[i - 1];
		curReserved.pointInTime += distance * curReserved.speed;
		// binser
		curReserved.pointInTime = max(curReserved.pointInTime,
								      position > 0 ? precompute[i][position - 1].pointInTime : LLONG_MIN);
		//~ cout << "Here " << curReserved.pointInTime << endl;
		position = upper_bound(all(sortedPrecompute[i]), curReserved) 
						- begin(sortedPrecompute[i]);
	}
	return curReserved.pointInTime;
}
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));
    initDP();
    vector <PLL> candidate;
    for(int i = 0;i < n;i++){
		candidate.emplace_back(busList[i].pointInTime, 0);
		if(i) candidate.emplace_back((busList[i].pointInTime + busList[i - 1].pointInTime) / 2, 0);
		else candidate.emplace_back(busList[i].pointInTime / 2, 0);
	}
	sort(all(candidate));
	candidate.erase(unique(all(candidate)), end(candidate));
	for(int i = 0;i < sz(candidate);i++){
		//~ cout << cari[i].fi << endl;
		candidate[i].se = arrival_pre(candidate[i].fi);
		cari.insert(candidate[i]);
	}
	//~ cout << "here " << sz(cari) << endl;
    return;
}



long long arrival_time(long long Y){
	auto it = upper_bound(all(cari), PLL(Y, 0));
	//~ cout << "Here " << endl;
	if(it == begin(cari)){
		//~ cout << "Begin " << endl;
		return Y + roadLength * reserved.speed; 
	} else {
		if(it != cari.end()) {
			auto pre = prev(it);
			LL atas = (*it).se;
			LL bawah = (*pre).se;
			//~ cout << "here " << atas << " " << bawah << endl;
			if(atas == bawah) return atas;
			LL tmp = arrival_pre(Y);
			cari.insert({Y, tmp});
			return tmp;
		} else {
			//~ cout << "Here " << endl;
			return max(Y + roadLength * reserved.speed, (*(prev(it))).se);
		}
		//~ cout << (*it).fi << " " << (*it).se << endl;
	}
	return 0;
}