Background

Translated from T4 “Rolete” of COCI 2023/2024 Contest #5

Problem Description

On a Saturday afternoon, Luka woke up from a nap and remembered that COCI is today. Before the contest, he only needs to do one thing: pull up the curtains.

In Luka’s room, there are $n$ curtains. For the $i$-th curtain, it is lowered by $a_i$ centimeters from the top of the window. He can pull up the curtains in two ways:

• He can start pulling up any one curtain manually. With this method, pulling up $1$ centimeter takes $t$ seconds.
• He can press a button, and all curtains will be pulled up together at the same speed, in sync.

When the button is pressed, the lifting speed is defined as follows: if all curtains are moving up, each curtain rises by $1$ centimeter in $s$ seconds. If $r$ curtains are already fully raised, this will slow down the system. Then each remaining curtain needs $s + k \cdot r$ seconds to rise by $1$ centimeter.

COCI is about to start, and Luka wants to raise his curtains as fast as possible. Meanwhile, his brother Marin walks into the room and asks him $q$ questions: What is the minimum time needed so that the maximum lowered height of the curtains does not exceed $h$ centimeters? For each question, Marin always considers the initial state of the curtains.

They realized there was not enough time to think about this before COCI. Luckily, this problem also appears here! Help them solve it.

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

Input Format

The first line contains four integers $n, t, s, k\ (1\le n,t,s\le 10^5,0\le k\le 10^5)$, representing the number of curtains, the time needed to manually raise curtains, the time needed when pressing the button, and the slowdown factor for synchronized lifting.

The second line contains $n$ integers $a_i\ (0\le a_i\le 10^5)$, describing the initial state of the curtains.

The third line contains an integer $q\ (1\le q\le 10^5)$, representing the number of questions.

The fourth line contains $q$ integers $h_i\ (0\le h_i\le 10^5)$, representing the maximum curtain height.

Output Format

Output one line with $q$ integers. The $i$-th integer is the minimum time needed so that the maximum lowered height of the curtains does not exceed $h_i$ centimeters.

3 2 5 1
2 2 4
3
2 0 1

4 14 9

2 3 4 0
3 1
3
3 2 0

0 3 10

4 3 10 3
2 4 5 6
3
4 3 0

9 18 47

Hint

Sample Explanation 1

To make the lowered height of all curtains at most $2$ centimeters, Luka needs to manually raise the third curtain by $2$ centimeters. The fastest way is to raise it manually, which will take him $4$ seconds.

If all curtains need to be fully raised, Luka can first manually raise the third curtain by $2$ centimeters. Then he can press the button and let all curtains rise by $2$ centimeters together. The total time needed is $4 + 10 = 14$ seconds.

Similarly, if the lowered height of the curtains must be at most $1$ centimeter, Luka will first manually raise the third curtain by $2$ centimeters, and then raise all curtains together by $1$ centimeter. The total raising time will be $9$ seconds.

Subtasks

Translated by ChatGPT 5