Amulets

题目描述

洞穴里有 $N$ 只怪物：怪物 $1$、怪物 $2$、$\ldots$、怪物 $N$。每只怪物有一个正整数的攻击力和一个表示为 $1$ 到 $M$ 之间整数的种类。 具体地，对于 $i = 1, 2, \ldots, N$，怪物 $i$ 的攻击力和种类分别为 $A_i$ 和 $B_i$。 Takahashi 将带着生命值为 $H$ 的生命和若干个 $M$ 个护符中的部分：护符 $1$、护符 $2$、$\ldots$、护符 $M$ 前往这个洞穴冒险。 在冒险中，Takahashi 按照顺序对 $i = 1, 2, \ldots, N$ 执行以下步骤（只要他的生命值没有降到 $0$ 或以下）。

如果 Takahashi 没有携带护符 $B_i$，怪物 $i$ 会攻击他并使他的生命值减少 $A_i$。 然后， 如果他的生命值大于 $0$，他击败怪物 $i$； 否则，他在未击败怪物 $i$ 的情况下死亡并结束冒险。

对于每个 $K = 0, 1, \ldots, M$ 独立求解下面的问题。

当在冒险中选择携带 $M$ 个护符中的 $K$ 个时，求 Takahashi 能击败的最大怪物数量。

约束保证对于每个 $i = 1, 2, \ldots, M$ 至少存在一只种类为 $i$ 的怪物。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $H$ $A_1$ $B_1$ $A_2$ $B_2$ $\vdots$ $A_N$ $B_N$

输出格式

对于每个 $i = 0, 1, 2, \ldots, M$，记 $X_i$ 为当 $K = i$ 时 Takahashi 能击败的最大怪物数量。 以以下格式输出 $X_0, X_1, \ldots, X_M$，用空格分隔： $X_0$ $X_1$ $\ldots$ $X_M$

7 3 7
3 2
1 1
4 2
1 2
5 1
9 3
2 3

2 5 7 7

15 5 400
29 5
27 4
79 1
27 2
30 3
4 1
89 2
88 3
75 5
3 1
39 4
12 1
62 4
38 2
49 1

8 12 15 15 15 15

提示

$1 \leq M \leq N \leq 3 \times 10^5$ $1 \leq H \leq 10^9$ $1 \leq A_i \leq 10^9$ $1 \leq B_i \leq M$ 对于每个 $1 \leq i \leq M$，存在 $1 \leq j \leq N$ 使得 $B_j = i$。 所有输入值均为整数。考虑 $K = 1$ 的情况。在这里，Takahashi 可以携带护符 $2$ 来击败最多的怪物，数量为 $5$。 冒险过程如下。

对于 $i = 1$，由于他有护符 $2$，他避免了怪物 $1$ 的攻击。然后，他击败了怪物 $1$。 对于 $i = 2$，由于他没有护符 $1$，他承受了怪物 $2$ 的攻击，生命变为 $6$。然后，他击败了怪物 $2$。 对于 $i = 3$，由于他有护符 $2$，他避免了怪物 $3$ 的攻击。然后，他击败了怪物 $3$。 对于 $i = 4$，由于他有护符 $2$，他避免了怪物 $4$ 的攻击。然后，他击败了怪物 $4$。 对于 $i = 5$，由于他没有护符 $1$，他承受了怪物 $5$ 的攻击，生命变为 $1$。然后，他击败了怪物 $5$。 对于 $i = 6$，由于他没有护符 $3$，他承受了怪物 $6$ 的攻击，生命变为 $-8$。然后，他在未击败怪物 $6$ 的情况下死亡并结束冒险。

类似地，当 $K=0$ 时，他可以击败 $2$ 只怪物；当 $K=2$ 时，通过携带护符 $2$ 和 $3$，他可以击败全部 $7$ 只怪物；当 $K=3$ 时，通过携带护符 $1$、$2$ 和 $3$，他可以击败全部 $7$ 只怪物。

标签: AtCoder|abc314G

来源

AtCoder|abc314G