P16370 [OOI 2026] Monsters and Swords

有 $n$ 只怪物排成一行，每只怪物有两个已知值：$h_i$ —— 怪物的生命值，以及 $r_i$ —— 击败这只怪物所获得的奖励，以硬币计。骑士必须击败所有怪物。 为了与怪物战斗，骑士拥有 $m$ 种剑，每种剑的特性已知：$s_j$ —— 剑的攻击力，$c_j$ —— 剑的价格（以硬币计）。要购买价格为 $c_j$ 的剑，骑士必须至少拥有 $c_j$ 枚硬币。购买后，骑士的硬币数将减少 $c_j$。初始时，骑士拥有 $x$ 枚硬币。 购买一把剑后，它最多可以在与怪物的战斗中使用 $k$ 次。任意种类的剑都可以购买任意次数。攻击力为 $s_j$ 的剑可以杀死生命值为 $h_i$ 的怪物，当且仅当 $s_j \geq h_i$。骑士在任何时刻只能拥有一把剑，这意味着购买一把新剑后，旧剑将不能再使用（但将来可以再次购买）。 怪物必须按固定顺序被击败：从第一只到最后一只。需要判断骑士能否做到这一点。

第一行包含四个整数 $n$、$m$、$k$ 和 $x$（$1 \le n, m \le 500\,000$，$1 \le k \le n$，$1 \le x \le 10^9$）—— 怪物数量、剑的种类数、一把剑最多可使用的次数，以及骑士初始拥有的硬币数。 接下来的 $n$ 行，描述怪物。第 $i$ 行包含两个整数：$h_i$ 和 $r_i$（$1 \le h_i, r_i \le 10^9$）—— 第 $i$ 只怪物的生命值和击败其获得的奖励。 再接下来的 $m$ 行，描述剑的特性。第 $j$ 行包含两个整数 $s_j$ 和 $c_j$（$1 \le s_j, c_j \le 10^9$）—— 第 $j$ 种剑的攻击力和价格。

如果骑士可以击败所有怪物，输出 $\texttt{Yes}$（不含引号），否则输出 $\texttt{No}$（不含引号）。

### 样例解释 在第一个例子中，骑士可以首先购买第三把剑，用它击败第一只和第二只怪物。此后，他将拥有 $5 - 1 + 1 + 5 = 10$ 枚硬币。这使他能够购买第一把剑并击败最后一只怪物。 在第二个例子中，骑士无法击败所有怪物，因为没有哪种剑能够击败第五只怪物。 ### 计分 本题的测试数据分为 9 组。每组仅在通过该组内全部测试以及此前某些组的全部测试后，才能获得分数。注意，某些组不要求通过题面中的样例。**离线测试** 表示你提交的解答在该组上的测试结果将仅在比赛结束后公布。每组的最终得分等于你所有提交的解答中在该组测试上获得的最高分。 | 子任务编号 | 分数 | 附加限制 | < | < | 必过组别 | 备注 | | :---: | :---: | :---: | :---: | :---: | :---: | :---: | | | | $n$ | $m$ | $k$ | | | | $0$ | $0$ | $--$ | $--$ | $--$ | $--$ | 题面中的样例。 | | $1$ | $11$ | $--$ | $--$ | $k=1$ | $--$ | $--$ | | $2$ | $9$ | $n \leq 100$ | $m \leq 100$ | $k=n$ | $--$ | $--$ | | $3$ | $14$ | $n \leq 100\,000$ | $m \leq 3000$ | $k=n$ | $2$ | $--$ | | $4$ | $16$ | $--$ | $--$ | $k=n$ | $2, 3$ | $--$ | | $5$ | $7$ | $n \leq 400$ | $m \leq 400$ | $--$ | $0, 2$ | $--$ | | $6$ | $8$ | $n \leq 3000$ | $m \leq 3000$ | $--$ | $0, 2, 5$ | $--$ | | $7$ | $10$ | $n \leq 150\,000$ | $m \leq 150\,000$ | $--$ | $0, 2, 3, 5, 6$ | $--$ | | $8$ | $12$ | $n \leq 300\,000$ | $m \leq 300\,000$ | $--$ | $0, 2, 3, 5$ -- $7$ | $--$ | | $9$ | $13$ | $--$ | $--$ | $--$ | $0$ -- $8$ | **离线测试。** | 翻译由 DeepSeek V4 Pro 完成