第 3 题 Rolete (`rolete`)

时间限制 1.0 s · 空间限制 256 MB · 49 个测试点 · 全文比较（过滤行末空格及文末回车）

本题使用文件输入输出：输入文件 rolete.in，输出文件 rolete.out。

译自 COCI 2023/2024 Contest #5 T4 「Rolete」

题目描述

一个周六的下午，Luka 从午睡中醒来，想起今天有 COCI！在比赛前，他只需要做一件事情：拉起窗帘。

卢卡的房间里有 $n$ 个窗帘，其中第 $i$ 个窗帘距离窗户顶部下降了 $a_i$ 厘米。他可以通过两种方式拉起窗帘：

按下按钮时，窗帘的上升速度定义如下：如果所有窗帘都在上升，每个窗帘都会在 $s$ 秒内上升 1 厘米。如果 $r$ 个窗帘已经完全升起，这会减慢系统的速度。那么剩余的窗帘每上升 1 厘米需要 $s + k \cdot r$ 秒钟。

COCI 即将开始，Luka 希望尽快拉起他的窗帘。与此同时，他的兄弟 Marin 走进房间，问了他 $q$ 个问题：为了使窗帘下降的最大高度不超过 $h_i$ 厘米，你需要的最短时间是多少？ Marin 对于每个问题都考虑窗帘的初始状态。

他们意识到在 COCI 之前没有足够的时间来考虑这个问题。幸运的是，这个问题也出现在这里！帮助他们解决它！

注意：Luka 总是将窗帘拉起一个整数值的厘米。

第一行四个整数 $n, t, s, k$ （ $1 \le n, t, s \le 10^5$ ， $0 \le k \le 10^5$ ），分别表示窗帘个数，手动拉窗帘所需的时间，按下按钮拉窗帘所需的时间和同步上升的减慢因子。

第二行包含 $n$ 个整数 $a_i$ （ $0 \le a_i \le 10^5$ ），表示初始窗帘的状态。

第三行包含一个整数 $q$ （ $1 \le q \le 10^5$ ），表示问题个数。

第四行包含 $q$ 个整数 $h_i$ （ $0 \le h_i \le 10^5$ ），表示最大窗帘高度。

输出一行 $q$ 个整数，第 $i$ 个表示使得窗帘下降的最大高度不超过 $h_i$ 厘米所需的最短用时。

输入：

输出：

4 14 9

输入：

输出：

0 3 10

输入：

输出：

9 18 47

为了使所有窗帘的下降高度最多为 2 厘米，卢卡需要手动将第三个窗帘拉起 2 厘米。最快的方法是手动拉起它，这将花费他 4 秒钟。

如果所有窗帘都需要完全拉起，卢卡可以先手动将第三个窗帘拉起 2 厘米。然后，他可以按下按钮，让所有窗帘同时上升 2 厘米。总共需要的时间为 $4 + 10 = 14$ 秒。

类似地，如果窗帘的下降高度最多为 1 厘米，卢卡会先手动将第三个窗帘拉起 2 厘米，然后将所有窗帘一起上升 1 厘米。拉起的总时间将为 9 秒。