[AdditionalFile4018.zip](file://AdditionalFile4018.zip?type=additional_file)

#4018. 「CEOI2023」Bring Down the ̶S̶k̶y̶ Grading Server

标签: 传统 | 时间限制: 4000 ms | 内存限制: 1024 MiB |

题目描述

题目译自 CEOI 2023 Day1 T2「Bring Down the Sky Grading Server」

尽管油量不足，开幕式还是取得了巨大成功（至少忽略舞台在 $10^{17}$ 名演员的重压下轰然倒塌的场面）。现在，委员会正期待着第一个比赛日。但是这是什么？技术委员会主席注意到了一些可疑的网络活动——显然有人计划黑掉测评服务器！

测评服务器的算力为 $c_G$，这个神秘的黑客会尝试将其降为 $0$。但是这个服务器同样被 $f_G$ 个防火墙保护，每个防火墙会将任意攻击的影响减少一个固定值 $S$。在每个时刻，黑客可以决定：

• 要么攻破一个防火墙，永久地将 $f_G$ 减一（最多减到 $0$），或者
• 要么使用他所有的算力 $c_H$ 去攻击服务器，永久地将 $c_G$ 减 $\max\{c_H-f_G\cdot S,0\}$。

然而，主席可以通过要么攻破黑客的 $f_H$ 个防火墙中的一个，或者使用测评服务器的算力攻击黑客，使 $c_H$ 减 $\max\{c_G-f_H\cdot S,0\}$ 来反击。主席和黑客轮流行动，黑客先手。

委员会直到攻击开始才会知道黑客拥有多少算力和防火墙。同时，由于委员会可能还可以升级服务器，它的算力和防火墙数也是不知道的。为了计划防御方案，委员会需要一个程序，对于 $Q$ 个不同的场景 $(c_H,f_H,c_G,f_G)$，如果主席采用最优策略，黑客是否可以攻破测评系统。

输入格式

第一行包含整数 $S$ 和 $Q$。

接下来 $Q$ 行，每行四个整数 $c_H,f_H,c_G,f_G$，分别表示神秘黑客和测评服务器所拥有的算力和防火墙数。

输出格式

输出 $Q$ 行，如果在这个场景下，无论主席如何操作，黑客总可以将测评服务器的算力减到 $0$ 或以下，输出 YES，否则输出 NO。

样例 1

输入

17 2
42 1 33 1
42 1 33 7

输出

YES
NO

考虑第一个样例的第一个场景：

• 在最开始，黑客可以攻击测评服务器，将 $c_G$ 减少 $42-1\cdot 17=25$ 到新的值 $8$。
• 之后，主席不能通过攻击减少黑客的算力，所以唯一合理的操作是攻破黑客唯一的防火墙。
• 然而，黑客可以直接通过另一次攻击，将测评服务器的算力减为 $8-25=-17\le 0$，这样就攻破了服务器并毁了第一个比赛日。

另一方面，在第二个场景中：

• 在最开始，黑客唯一能做的事情就是攻破其中一个防火墙。
• 之后，主席可以攻击黑客，将黑客的算力 $c_H$ 减为 $26$。
• 在之后的两轮，黑客能做的也只有攻破其中一个防火墙，而主席每次都可以进行攻击，这样将 $c_H$ 减到小于 $0$，并成功地击退了黑客的攻击。

样例 2

输入

1 1
999999999999 999999999999 999999999999 999999999999

输出

YES

样例 3

输入

2 1
1000000000000 0 1 1000000000000

输出

NO

数据范围与提示

对于所有数据，$1\le S\le 3\times 10^4,1\le c_H,c_G\le 10^{12},0\le f_H,f_G\le 10^{12},1\le Q\le 2.5\times 10^5$。

详细子任务附加限制及分值如下表所示。