311014: CF1921C. Sending Messages

C. Sending Messagestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Stepan is a very busy person. Today he needs to send $n$ messages at moments $m_1, m_2, \dots m_n$ ($m_i < 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.

Input

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 < 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$.

Output

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.

ExampleInput

6
1 3 1 5
3
7 21 1 3
4 6 10 13 17 20 26
5 10 1 2
1 2 3 4 5
1 1000000000 1000000000 1000000000
1000000000
3 11 9 6
6 8 10
12 621526648 2585904 3566299
51789 61859 71998 73401 247675 298086 606959 663464 735972 806043 806459 919683

Output

NO
YES
YES
NO
NO
YES

Note

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.

题目大意：
Stepan是一个很忙的人，今天他需要在不同时刻发送n条消息，这些时刻分别是m_1, m_2, ..., m_n（m_i < m_{i+1}）。不幸的是，在时刻0，他的手机只剩下f单位的电量。手机每开启一单位时间就会消耗a单位的电量。此外，Stepan可以在任何时刻关闭手机，并在之后再次开启，这个操作每次会消耗b单位的电量。如果在任何时候电量降为0（变为≤0），那么在那个时刻就无法发送消息。因为所有的消息对Stepan来说都非常重要，他想知道在不充电的情况下是否可以发送所有消息。

输入数据格式：
输入的第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是t个测试用例的描述。
每个测试用例的第一行包含四个整数n, f, a, b（1 ≤ n ≤ 2 * 10^5, 1 ≤ f, a, b ≤ 10^9）——消息的数量、手机的初始电量、每单位时间的电量消耗以及在关闭和开启手机时的电量消耗。
每个测试用例的第二行包含n个整数m_1, m_2, ..., m_n（1 ≤ m_i ≤ 10^9, m_i < m_{i+1}）——需要发送消息的时刻。
保证在一个测试中，所有测试用例的n之和不超过2 * 10^5。

输出数据格式：
对于每个测试用例，如果Stepan可以发送所有消息，输出"YES"，否则输出"NO"。
输出每个字母可以是任何大小写。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。

示例：
输入：
6
1 3 1 5
3
7 21 1 3
4 6 10 13 17 20 26
5 10 1 2
1 2 3 4 5
1 1000000000 1000000000 1000000000
1000000000
3 11 9 6
6 8 10
12 621526648 2585904 3566299
51789 61859 71998 73401 247675 298086 606959 663464 735972 806043 806459 919683
输出：
NO
YES
YES
NO
NO
YES

注意：
在第一个测试用例中，如果不关闭手机，到时刻3时，手机电量将为0，无法发送消息。如果关闭再开启，手机电量将减少5单位，也无法发送消息。
在第三个测试用例中，通过在适当的时候关闭和开启手机，可以在所有时刻发送消息。题目大意： Stepan是一个很忙的人，今天他需要在不同时刻发送n条消息，这些时刻分别是m_1, m_2, ..., m_n（m_i < m_{i+1}）。不幸的是，在时刻0，他的手机只剩下f单位的电量。手机每开启一单位时间就会消耗a单位的电量。此外，Stepan可以在任何时刻关闭手机，并在之后再次开启，这个操作每次会消耗b单位的电量。如果在任何时候电量降为0（变为≤0），那么在那个时刻就无法发送消息。因为所有的消息对Stepan来说都非常重要，他想知道在不充电的情况下是否可以发送所有消息。 输入数据格式： 输入的第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。接下来是t个测试用例的描述。 每个测试用例的第一行包含四个整数n, f, a, b（1 ≤ n ≤ 2 * 10^5, 1 ≤ f, a, b ≤ 10^9）——消息的数量、手机的初始电量、每单位时间的电量消耗以及在关闭和开启手机时的电量消耗。 每个测试用例的第二行包含n个整数m_1, m_2, ..., m_n（1 ≤ m_i ≤ 10^9, m_i < m_{i+1}）——需要发送消息的时刻。 保证在一个测试中，所有测试用例的n之和不超过2 * 10^5。 输出数据格式： 对于每个测试用例，如果Stepan可以发送所有消息，输出"YES"，否则输出"NO"。 输出每个字母可以是任何大小写。例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。 示例： 输入： 6 1 3 1 5 3 7 21 1 3 4 6 10 13 17 20 26 5 10 1 2 1 2 3 4 5 1 1000000000 1000000000 1000000000 1000000000 3 11 9 6 6 8 10 12 621526648 2585904 3566299 51789 61859 71998 73401 247675 298086 606959 663464 735972 806043 806459 919683 输出： NO YES YES NO NO YES 注意： 在第一个测试用例中，如果不关闭手机，到时刻3时，手机电量将为0，无法发送消息。如果关闭再开启，手机电量将减少5单位，也无法发送消息。 在第三个测试用例中，通过在适当的时候关闭和开启手机，可以在所有时刻发送消息。