#5740. 「OOI 2026 Day2」怪物与长剑

标签: 传统 | 时间限制: 1000 ms | 内存限制: 512 MiB |

题目描述

题目译自 Open Olympiad in Informatics 2026 Day2 T4 「Монстры и мечи」 / 「Monsters and Swords」。

给定 $n$ 个排成一排的怪物。对于每个怪物，已知两个数值：$h_i$ 表示怪物的生命值，$r_i$ 表示击败该怪物后获得的金币奖励。骑士需要依次击败所有的怪物。

为了与怪物战斗，骑士拥有 $m$ 种类型的长剑。每种长剑都有其性能参数：$s_j$ 表示长剑的力量，$c_j$ 表示购买该长剑所需的金币价格。若要购买价格为 $c_j$ 的长剑，骑士必须拥有至少 $c_j$ 枚金币。购买长剑后，骑士拥有的金币数量会减少 $c_j$。最初，骑士拥有 $x$ 枚金币。

购买一把长剑后，在与怪物的战斗中最多可以使用 $k$ 次。每种类型的长剑都可以购买任意次数。若长剑的力量 $s_j \geq h_i$，则该长剑可以杀死生命值为 $h_i$ 的怪物。在任何时刻，骑士只能拥有一把长剑，这意味着在购买新长剑后，旧长剑将无法再被使用（但以后可以再次购买之前类型的长剑）。

怪物必须按固定的顺序被击败：从第一个到最后一个。你需要判断骑士是否能够完成这一任务。

输入格式

第一行包含四个整数 $n, m, k$ 和 $x$ $(1 \leq n, m \leq 500000, 1 \leq k \leq n, 1 \leq x \leq 10^9)$，分别表示怪物的数量、长剑类型的数量、长剑的最大使用次数以及骑士初始拥有的金币数量。

接下来的 $n$ 行给出怪物的描述。其中第 $i$ 行包含两个整数 $h_i$ 和 $r_i$ $(1 \leq h_i, r_i \leq 10^9)$，分别表示第 $i$ 个怪物的生命值和击败它后的奖励。

接下来的 $m$ 行给出长剑特性的描述。其中第 $j$ 行包含两个整数 $s_j$ 和 $c_j$ $(1 \leq s_j, c_j \leq 10^9)$，分别表示第 $j$ 种长剑的力量和价格。

输出格式

如果骑士可以击败所有怪物，输出 Yes，否则输出 No。

样例 1

输入

3 3 2 5
1 1
5 5
9 5
9 10
1 1
5 1

输出

Yes

在第一个样例中，骑士可以先购买第三种长剑，利用它击败第一个和第二个怪物。在此之后，他将拥有 $5 - 1 + 1 + 5 = 10$ 枚金币。凭借这些金币，他可以购买第一种长剑并击败最后一个怪物。

样例 2

输入

5 5 5 6
3 6
2 4
1 1
4 4
8 4
2 7
7 7
3 4
5 9
6 4

输出

No

在第二个样例中，骑士无法击败所有怪物，因为没有任何一种长剑可以击败第五个怪物。

数据范围与提示

详细子任务附加限制及分值如下表所示。其中子任务 $0$ 是样例。