Stepan 是一个非常忙碌的人。今天他需要在 $$$m_1, m_2, \dots m_n$$$ ($$$m_i < m_{i + 1}$$$) 时刻发送 $$$n$$$ 消息。不幸的是,此时 $$$0$$$,他的手机只剩下 $$$f$$$ 电量。此时$$$0$$$,手机已开机。
手机每开启一个时间单位就会损失 $$$a$$$ 单位的电量。此外,Stepan 可以随时关闭手机并稍后再打开。此动作每次消耗 $$$b$$$ 单位的能量。考虑打开和关闭是瞬时的,因此您可以在$$$x$$$时刻打开它并在同一时刻发送消息,反之亦然,在$$$x$$$时刻发送消息并在同一时刻关闭手机。
如果在任何时候电量水平下降到 $$$0$$$(变为 $$$\le 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$$$, $$$m_i < m_{i + 1}$$$) — 需要发送消息的时刻。
保证在测试中所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,如果 Stepan 可以发送所有消息,则输出“YES”,否则输出“NO”。
您可以以任何大小写(小写或大写)输出每个字母。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被接受为肯定答案。
示例
输入 #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
输出 #1
NO YES YES NO NO YES
注意
在示例的第一个测试用例中,在 $$$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$$$ 时刻发送消息。
如果您的解决方案中存在整数溢出,示例的最后一个(第六个)测试集可能会失败。