CF1921C.Sending Messages

Stepan is a very busy person. Today he needs to send $n$ messages at moments $m_1, m_2, \dots m_n$ ($m_i \lt m_{i + 1}$). Unfortunately, by the moment $0$, his phone only has $f$ units of charge left. At the moment $0$, the phone is turned on.

The phone loses $a$ units of charge for each unit of time it is on. Also, at any moment, Stepan can turn off the phone and turn it on later. This action consumes $b$ units of energy each time. Consider turning on and off to be instantaneous, so you can turn it on at moment $x$ and send a message at the same moment, and vice versa, send a message at moment $x$ and turn off the phone at the same moment.

If at any point the charge level drops to $0$ (becomes $\le 0$), it is impossible to send a message at that moment.

Since all messages are very important to Stepan, he wants to know if he can send all the messages without the possibility of charging the phone.

斯捷潘是一个非常忙碌的人。今天，他需要在时刻 $m_1, m_2, \dots, m_n$（其中 $m_i < m_{i+1}$）发送 $n$ 条消息。不幸的是，在时刻 $0$，他的手机仅剩 $f$ 单位电量。在时刻 $0$，手机处于开机状态。

手机每开机一单位时间，将消耗 $a$ 单位电量。此外，在任意时刻，斯捷潘都可以关机，并在之后再次开机；每次开关机操作均消耗 $b$ 单位电量。假设开关机操作是瞬时完成的，因此他可以在时刻 $x$ 开机并同时发送消息，反之亦然——即可以在时刻 $x$ 发送消息后立即关机。

若在任意时刻电量降至 $0$（即 $\le 0$），则无法在该时刻发送消息。

由于所有消息对斯捷潘都至关重要，他想知道：在无法为手机充电的前提下，能否成功发送全部消息？

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by the descriptions of the test cases.

The first line of each test case contains four integers $n$, $f$, $a$, and $b$ ($1 \le n \le 2 \cdot 10^5$, $1 \le f, a, b \le 10^9$) — the number of messages, the initial phone's charge, the charge consumption per unit of time, and the consumption when turned off and on sequentially.

The second line of each test case contains $n$ integers $m_1, m_2, \dots, m_n$ ($1 \le m_i \le 10^9$, $m_i \lt m_{i + 1}$) — the moments at which messages need to be sent.

It is guaranteed that in a test the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含四个整数 $n$、$f$、$a$ 和 $b$（$1 \le n \le 2 \cdot 10^5$，$1 \le f, a, b \le 10^9$），分别表示消息数量、手机初始电量、单位时间的耗电量，以及依次关机再开机的耗电量。

每个测试用例的第二行包含 $n$ 个整数 $m_1, m_2, \dots, m_n$（$1 \le m_i \le 10^9$，且 $m_i \lt m_{i + 1}$），表示需要发送消息的时刻。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, output "YES" if Stepan can send all the messages, and "NO" otherwise.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

对于每个测试用例，如果 Stepan 能够发送所有消息，则输出 “YES”，否则输出 “NO”。

您可以以任意大小写形式输出每个字母（小写或大写）。例如，字符串 “yEs”、“yes”、“Yes” 和 “YES” 均会被接受为肯定回答。

In the first test case of the example, at moment $0$, the phone's charge is $3$. When sending a message at moment $3$ without turning it off, $(3 - 0) \cdot 1 = 3$ units of charge will be spent. In this case, the charge will drop to $0$ and Stepan will not be able to send the message. When turning off and on, the phone's charge will decrease by $5$, so it will not be possible to send the message in this way.

In the third test case of the example, at moment $0$, the phone's charge is $10$. The phone loses $1$ unit of charge per unit of time, and when turned off and on, it loses $2$ units of charge. To send all messages, the following actions can be taken:

• Turn off the phone at moment $0$ and turn it on at moment $1$, after which $10 - 2 = 8$ units of charge will remain;
• send a message at moment $1$;
• send a message at moment $2$, after which $8 - (2 - 1) \cdot 1 = 7$ units of charge will remain;
• Turn off the phone at moment $2$ and turn it on at moment $3$, after which $7 - 2 = 5$ units of charge will remain;
• send a message at moment $3$;
• Turn off the phone at moment $3$ and turn it on at moment $4$, after which $5 - 2 = 3$ units of charge will remain;
• send a message at moment $4$;
• Turn off the phone at moment $4$ and turn it on at moment $5$, after which $3 - 2 = 1$ unit of charge will remain;
• send a message at moment $5$.

The last (sixth) test set of the example may fail if there is an integer overflow in your solution.

在示例的第一个测试用例中，时刻 $0$ 时手机电量为 $3$。若在时刻 $3$ 发送消息且不关机，则将消耗 $(3 - 0) \cdot 1 = 3$ 单位电量。此时电量将降至 $0$，Stepan 将无法发送该消息。若选择关机再开机，则手机将额外消耗 $5$ 单位电量，因此这种方式也无法成功发送消息。

在示例的第三个测试用例中，时刻 $0$ 时手机电量为 $10$。手机每单位时间自然耗电 $1$ 单位；而每次关机再开机将额外消耗 $2$ 单位电量。为成功发送全部消息，可执行如下操作：

• 在时刻 $0$ 关机，并于时刻 $1$ 开机，此时剩余电量为 $10 - 2 = 8$；
• 在时刻 $1$ 发送一条消息；
• 在时刻 $2$ 发送一条消息，此时剩余电量为 $8 - (2 - 1) \cdot 1 = 7$；
• 在时刻 $2$ 关机，并于时刻 $3$ 开机，此时剩余电量为 $7 - 2 = 5$；
• 在时刻 $3$ 发送一条消息；
• 在时刻 $3$ 关机，并于时刻 $4$ 开机，此时剩余电量为 $5 - 2 = 3$；
• 在时刻 $4$ 发送一条消息；
• 在时刻 $4$ 关机，并于时刻 $5$ 开机，此时剩余电量为 $3 - 2 = 1$；
• 在时刻 $5$ 发送一条消息。

示例中的最后一组（第六组）测试数据可能因你的解法中出现整数溢出而失败。