CF1921C Sending Messages

题目描述

Stepan是一个busy的人。今天，他需要在 $m_1,m_2,\dots m_n$ 时刻发送 $n$ 条信息。很惨的是，到 $0$ 时刻，他的手机只剩 $f$ 个单位电量。此时手机已开机。

手机每开机一时刻就会损失 $a$ 个单位电量。此外，Stepan可以随时关闭手机，稍后再开机，每次共消耗 $b$ 个单位的能量。开关机不花费任何时间，这样就可以在 $x$ 时刻打开它，同时发送信息，反之，在 $x$ 时刻发送信息同时关闭手机也是可以的。

如果在任何时候电量降至 $0$ 以下，则手机自动关机，无法发送消息。Stepan想知道是否可以在不给手机充电的情况下发送所有信息。

输入格式

本题包含多组测试数据。

第一行一个整数 $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$ ) ，保证其单调递增。

输出格式

对于每个测试用例，输出字符串 input1YES 或 output1NO 的一种，表示是否能发送所有信息。

输入输出样例 1

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