Overtaking

문제

There is a one-lane, one-way road from Budapest Airport to Hotel Forrás. The road is $LL$ kilometres long.

Over the IOI 2023 event, $N+1N+1$ transfer buses traverse this road. Buses are numbered from $00$ to $NN$. Bus $ii$ ($0\le i<N0\; \backslash le\; i\; \backslash lt\; N$) is scheduled to leave the airport at the $T[i]T[i]$-th second of the event, and can travel $11$ kilometre in $W[i]W[i]$ seconds. Bus $NN$ is a reserve bus that can travel $11$ kilometre in $XX$ seconds. The time $YY$ when it will leave the airport has not yet been decided.

Overtaking is not allowed on the road in general, but the buses are allowed to overtake each other at sorting stations. There are $MM$ ($M>1M\; \backslash gt\; 1$) sorting stations, numbered from $00$ to $M-1M\; -\; 1$, on different positions on the road. Sorting station $jj$ ($0\le j<M0\; \backslash le\; j\; \backslash lt\; M$) is located $S[j]S[j]$ kilometres from the airport along the road. The sorting stations are sorted in increasing distance from the airport, that is, $S[j]<S[j+1]S[j]\; \backslash lt\; S[j+1]$ for each $0\le j\le M-20\; \backslash le\; j\; \backslash le\; M\; -\; 2$. The first sorting station is the airport and the last one is the hotel, that is, $S[0]=0S[0]\; =\; 0$ and $S[M-1]=LS[M-1]\; =\; L$.

Each bus travels at maximum speed unless it catches up to a slower bus travelling ahead of it on the road, in which case they get bunched and forced to travel at the speed of the slower bus, until they reach the next sorting station. There, the faster buses will overtake the slower buses.

Formally, for each $ii$ and $jj$ such that $0\le i\le N0\; \backslash le\; i\; \backslash le\; N$ and $0\le j<M0\; \backslash le\; j\; \backslash lt\; M$, the time $t_{i,j}t\_\{i,j\}$ (in seconds) when bus $ii$ arrives at sorting station $jj$ is defined as follows. Let $t_{i,0}=T[i]t\_\{i,0\}\; =\; T[i]$ for each $0\le i<N0\; \backslash le\; i\; \backslash lt\; N$, and let $t_{N,0}=Yt\_\{N,0\}\; =\; Y$. For each $jj$ such that $0<j<M0\; \backslash lt\; j\; \backslash lt\; M$:

• Define the expected time of arrival (in seconds) of bus $ii$ at sorting station $jj$, denoted by $e_{i,j}e\_\{i,j\}$, as the time when bus $ii$ would arrive at sorting station $jj$ if it was travelling at full speed from the time it arrived at sorting station $j-1j-1$. That is, le
  • $e_{i,j}=t_{i,j-1}+W[i]\cdot (S[j]-S[j-1])e\_\{i,j\}\; =\; t\_\{i,j-1\}\; +\; W[i]\; \backslash cdot\; (S[j]-S[j-1])$ for each $0\le i<N0\; \backslash le\; i\; \backslash lt\; N$, and
  • $e_{N,j}=t_{N,j-1}+X\cdot (S[j]-S[j-1])e\_\{N,j\}\; =\; t\_\{N,j-1\}\; +\; X\; \backslash cdot\; (S[j]-S[j-1])$.
• Bus $ii$ arrives at sorting station $jj$ at the *maximum* of the expected times of arrivals of bus $ii$ and of every other bus that arrived at station $j-1j-1$ earlier than bus $ii$. Formally, let $t_{i,j}t\_\{i,j\}$ be the maximum of $e_{i,j}e\_\{i,j\}$ and every $e_{k,j}e\_\{k,j\}$ for which $0\le k\le N0\; \backslash le\; k\; \backslash le\; N$ and $t_{k,j-1}<t_{i,j-1}t\_\{k,j-1\}\; \backslash lt\; t\_\{i,j-1\}$.

The IOI organizers want to schedule the reserve bus (bus $NN$). Your task is to answer $QQ$ questions of the organizers, which are of the following form: given the time $YY$ (in seconds) when the reserve bus is supposed to leave the airport, at what time would it arrive at the hotel?