P9730 [CEOI 2023] Grading Server

翻译自 CEOI2023 Day1 T2 [Grading Server](https://www.ceoi2023.de/wp-content/uploads/2023/09/2-grading-server.pdf)。

竞赛委员会的主席注意到了一些可疑的网络活动 —— 有人想要攻击评测系统！ 评测系统拥有特定的算力 $c_G$。黑客会尝试将 $c_G$ 降为 $0$（甚至更低）。系统被 $f_G$ 个防火墙保护着，每个防火墙都会将攻击的影响降低 $S$。 每个时刻，黑客可以进行以下两种操作之一： - 击破一个防火墙，将 $f_G$ 降低 $1$（但不能低于 $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)$ 情况下，就算委员会主席采取了最优的行动，黑客是否依然能够击垮评测系统（将 $c_G$ 降低为 $0$ 或更低）。

第一行两个整数 $S, Q$。 接下来 $Q$ 行，每行四个整数 $c_H, f_H, c_G, f_G$ 描述一个情况，分别为黑客的算力和防火墙数量，以及评测系统的算力和防火墙数量。

你的程序应当输出 $Q$ 行，每行一个字符串 `YES` 或 `NO`。`YES` 表示无论委员会主席的行动如何，采取最优策略的黑客总能够让 $c_G$ 降为 $0$ 或更低；否则输出 `NO`。

#### 样例解释 考虑样例一的第一个情况： - 首先，黑客攻击评测系统，将 $c_G$ 降低 $42 - 1\cdot 17 = 25$ 为 $8$； - 接下来，委员会主席无法通过攻击降低 $c_H$，所以明智的选择是击破黑客的唯一的防火墙； - 然而，黑客可以继续攻击评测系统，将 $c_G$ 降低 $25$ 为 $-17\leq 0$，击垮评测系统并毁掉第一天比赛日。 对于第二个情况： - 一开始，黑客唯一能做的就是击破一个评测系统的防火墙； - 接下来，委员会主席攻击黑客，将 $c_H$ 降低为 $26$； - 接下来两轮，黑客同样只能攻击评测系统的防火墙。同时委员会主席每次攻击黑客，将 $c_H$ 降低为不大于 $0$ 的值，成功防御黑客的攻击。 #### 数据范围与约定 - Subtask 1（5 分）：$S, c_H, c_G, f_H, f_G\leq 75$； - Subtask 2（5 分）：$S, c_H, c_G, f_H, f_G\leq 300$； - Subtask 3（10 分）：$S = 1$； - Subtask 4（25 分）：$S, c_H, c_G, f_H, f_G\leq 2000$； - Subtask 5（20 分）：$S\leq 400$； - Subtask 6（20 分）：$f_H, f_G\leq 125$； - Subtask 7（15 分）：无特殊限制。 对于所有数据，$1\leq S\leq 3\times 10 ^ 4$，$1\leq c_H, c_G\leq 10 ^ {12}$，$0\leq f_H, f_G\leq 10 ^ {12}$，$1\leq Q\leq 2.5\times 10 ^ 5$。 #### 限制 时间：4s 空间：1GB