// Source: https://usaco.guide/general/io

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
int L, N = 0,X,M,Y, st;
vector<ll> T;
vector<int> W,S;
int id = 0;
vector<vector<int>> cars;
vector<vector<ll>> curT;
vector<vector<pair<int,int>>> takes;
vector<pair<ll,ll>> mem;
vector<vector<ll>> ans;

bool front(int x, int y) {
    return (curT[id][x] < curT[id][y] )
		|| (curT[id][x] == curT[id][y] && W[x] < W[y]);
}

void init(int a, int b, vector<ll> c, vector<int> d, int e, int f, vector<int> g) {
	L=a; /*N=b;*/ /*T=c;*/ /*W=d;*/ X=e; M=f; S = g;

	for (int i = 0; i < b; i ++) {
		if (d[i] > X) {
			//nvm dealt with 
			W.push_back(d[i] ); // minus X later 
			T.push_back(c[i]); // add X * L later
			N++;
		}
	}
	cars.resize(M);
	curT.resize(M);
	ans = vector<vector<ll>>(1000, vector<ll>(1000));
	takes = vector<vector<pair<int,int>>>(N, vector<pair<int,int>>(M, make_pair(-1,-1)));
	for (int i = 0; i < M; i ++) {
		curT[i].resize(N);
		cars[i].resize(N);
		for (int j = 0; j < N; j ++) {
			cars[i][j] = i;
			curT[0][j] = T[i];
		}
	}
	sort(cars[0].begin(),cars[0].end(), front);

	for (int i = 0; i < N; i ++) {
		takes[i][M-1] = make_pair(M,-1);
	}


	//pprecomputing arrival times
	for (int s = 1; s < M; s++) {
		ll dist = S[s] - S[s-1]; 
		ll mxt = 0, mcar = -1;
		for (int i = 0; i < N; i++) {
			int curc = cars[s-1][i];
			if (mxt < curT[s-1][curc] + W[curc] * dist) {
				//finding max
				mxt = curT[s-1][curc] + W[curc] * dist;
				mcar= curc;
			} else {
				if (takes[curc][i].ss == -1 || W[takes[curc][s].ss] < W[mcar]) {
					takes[curc][s] = make_pair(s, mcar);
				}
			}
			curT[s][curc] = mxt;
		}
		id = s;
		sort(cars[s].begin(), cars[s].end(), front);
	}
	
	for (int i = 0; i < N; i ++) {
		for (int j = M-2; j >= 0; j --) {
			if (takes[i][j].ff ==  -1) {
				takes[i][j] = takes[i][j+1];
			}
		}
	}
	//iinit finally done cant wait for arrivla tiem
}
int up(int s, int x, int y)
{
    if (Y <= curT[s][cars[s][0]])
        return -1;

    if (x == y)
        return cars[s][x];

    int half = (x + y + 1) / 2;
    if (curT[s][cars[s][half]] < Y)
        return up(s, half, y);
    return up(s, x, half - 1);
}

int down(int carId, int x, int y)
{
    if (x == y)
        return x;

    int half = (x + y) / 2;
    if (Y + X * (S[half] - S[st]) > curT[half][carId])
        return down(carId, half + 1, y);
    return down(carId, x, half);
}

ll arrival_time(int k) {
	Y = k;
	if (N == 0) {
		return Y + L * X;
	}
	st = 0;
	mem.clear();
	int bel = up(0,0,N-1);
	//cout << "!!\n";
	while (st != M-1 ) { //simulate
		if (bel == -1) {
			Y += X * (L - S[st]);
			break;
		}
		int pos = takes[bel][st+1].ff;
		int station = pos - 1;
        if (Y + (S[station] - S[st]) * X > curT[station][bel])
        {
            Y += (S[station] - S[st]) * X;
            bel = takes[bel][st + 1].ss;
            st = station;
        }
        else
        {
            int ost = down(bel, st, station);
            Y = curT[ost][bel];
            station = ost;
            if (bel != -1 && ans[st][bel] != 0)
            {
                Y = ans[st][bel];
                break;
            }
            mem.push_back({st, bel});
            bel = up(st, 0, N - 1);
        }
    }
    for (auto it : mem) {
        ans[it.ff][it.ss] = Y;
	}
    return Y;
}

/usr/bin/ld: /tmp/cc43moMu.o: in function `main':
implementer.cpp:(.text.startup+0x4c5): undefined reference to `arrival_time(long long)'
collect2: error: ld returned 1 exit status