Curtain Pull Challenge

On a Saturday afternoon, Luka wakes up from his nap and remembers that there is a COCI contest today. Before the contest begins, he must perform one important task – pull up the curtains in his room.

There are n curtains in Luka's room. The i-th curtain is currently hanging a_i centimeters below the top of the window. Luka can raise the curtains using one of the two methods:

• Manual pull: He can choose any curtain and pull it up manually. For this method, pulling the curtain up by 1 centimeter takes t seconds.
• Automatic (Button) pull: He can press a button that raises all curtains simultaneously. When the button is pressed, if all curtains are still rising then each curtain rises 1 centimeter in s seconds. However, once r curtains have been completely raised, the system slows down for the remaining curtains. In that case, every additional centimeter for the remaining curtains takes s + k\cdot r seconds.

For each curtain, Luka must raise it by an integer number of centimeters. His goal is to have every curtain raised enough so that the maximum length still hanging (i.e. the distance from the top) does not exceed h centimeters.

Formally, for each curtain i the required raise is at least max(0, a_i - h) centimeters. For the automatic method, suppose a set of curtains requiring a raise d₁, d₂, …, d_m (with d₁ \le d₂ \le ... \le d_m) is chosen. Then the total time needed if they are all raised with the button is:

\(T_{\text{button}} = d_1\cdot s + \sum_{i=2}^{m} (d_i - d_{i-1})\cdot (s + k\cdot (i-1))\)

If a curtain is raised manually, its raising time is d_i \cdot t seconds. Under the assumption that all operations start simultaneously, the finishing time for a curtain will be either the manual time or the time determined by the automatic system – whichever method is chosen. Luka can choose, for each curtain that requires lifting (that is, with a_i > h), whether to pull it manually or let the button mechanism raise it along with some other curtains. The overall finishing time is the maximum time among all curtains. Luka wants to minimize this overall time.

You are given q queries. In each query you are given a value h (and the initial state of the curtains remains the same). For each query, compute the minimum time required so that after raising the curtains by the chosen methods, the maximum remaining hanging length is at most h centimeters.

Note: Luka always raises a curtain by an integer number of centimeters.

inputFormat

The first line contains five integers: n, t, s, k, and q (the number of curtains, the time per cm for manual pull, the base time per cm for the button pull, the slowdown factor, and the number of queries, respectively).

The second line contains n integers: a₁, a₂, …, a_n representing the current lengths (in centimeters) by which the curtains hang below the top.

Each of the next q lines contains one integer h as described above.

outputFormat

For each query, output a single integer – the minimum time required (in seconds) so that after raising the curtains, the maximum hanging length is at most h centimeters.

sample

5 2 3 1 3
10 5 7 12 3
5
7
10

14
10
4

</p>