Overtaking

A one-lane, one-way road runs from Budapest Airport to Hotel Forrás. The road is $L$ kilometres long.

During the IOI 2023 event, $N+1$ transfer buses travel on this road. The buses are numbered from $0$ to $N$. Bus $i$ ($0 \le i < N$) is scheduled to leave the airport at the $T[i]$-th second of the event, and it can travel 1 kilometre in $W[i]$ seconds. Bus $N$ is a reserve bus that can travel 1 kilometre in $X$ seconds. The time $Y$ when the reserve bus leaves the airport has not been decided yet.

Overtaking is generally not allowed on the road. Instead, buses may overtake each other at sorting stations. There are $M$ sorting stations ($M > 1$), numbered from $0$ to $M-1$, at different positions on the road. Sorting station $j$ is $S[j]$ kilometres from the airport. The stations are in increasing order of distance, so $S[j] < S[j+1]$ for each $0 \le j \le M-2$. The first station is the airport and the last station is the hotel, so $S[0] = 0$ and $S[M-1] = L$.

A bus travels at its maximum speed unless it catches up to a slower bus ahead of it. In that case, the two buses bunch together and travel at the speed of the slower bus until they reach the next sorting station. There, the faster bus overtakes the slower one.

Formally, let $t_{i,j}$ be the time in seconds when bus $i$ arrives at sorting station $j$, for each $0 \le i \le N$ and $0 \le j < M$. Let $t_{i,0} = T[i]$ for $0 \le i < N$, and let $t_{N,0} = Y$. For each $0 < j < M$, define the expected time of arrival $e_{i,j}$ as the time bus $i$ would reach station $j$ if it travelled at full speed from station $j-1$:

$e_{i,j} = t_{i,j-1} + W[i] \cdot (S[j]-S[j-1]) \text{ for } 0 \le i < N$

$e_{N,j} = t_{N,j-1} + X \cdot (S[j]-S[j-1])$

Bus $i$ arrives at station $j$ at the maximum of $e_{i,j}$ and $e_{k,j}$ for every bus $k$ ($0 \le k \le N$) with $t_{k,j-1} < t_{i,j-1}$.

You must answer $Q$ queries. Each query gives the departure time $Y$ of the reserve bus. Find the time at which the reserve bus arrives at the hotel.

$1 \le L \le 10^9$, $1 \le N \le 1000$, $0 \le T[i] \le 10^{18}$ for each $i$ with $0 \le i < N$, $1 \le W[i] \le 10^9$ for each $i$ with $0 \le i < N$, $1 \le X \le 10^9$, $2 \le M \le 1000$, $0 = S[0] < S[1] < \cdots < S[M-1] = L$, $1 \le Q \le 10^6$, $0 \le Y \le 10^{18}$.