AT_abc314_g [ABC314G] Amulets

在洞窟中，有 $N$ 只怪兽，分别编号为 $1, 2, \ldots, N$。每只怪兽都有一个正整数的**攻击力**，以及一个用 $1$ 到 $M$ 之间的整数表示的**类型**。具体来说，对于 $i = 1, 2, \ldots, N$，第 $i$ 只怪兽的攻击力为 $A_i$，类型为 $B_i$。 高桥君将从 $M$ 个护身符（编号为 $1, 2, \ldots, M$）中选择若干个带上，并以体力 $H$ 的状态进入这个洞窟冒险。 在冒险过程中，高桥君会按照 $i = 1, 2, \ldots, N$ 的顺序，依次进行以下操作（只要体力没有降到 $0$ 或以下）： - 如果高桥君没有带上类型为 $B_i$ 的护身符，则会受到第 $i$ 只怪兽的攻击，体力减少 $A_i$。 - 在此之后，如果高桥君的体力仍然大于 $0$，则他可以击败第 $i$ 只怪兽。 - 如果体力降为 $0$ 或以下，则无法击败第 $i$ 只怪兽，冒险结束。 请你对于 $K = 0, 1, \ldots, M$ 的每一种情况，独立地解决如下问题： > 高桥君从 $M$ 个护身符中选择 $K$ 个带上去冒险时，他最多能击败多少只怪兽？ 另外，保证对于任意 $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$ 时高桥君最多能击败的怪兽数。请按如下格式，用空格分隔输出 $X_0, X_1, \ldots, X_M$。 > $X_0$ $X_1$ $\ldots$ $X_M$

### 约束条件 - $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$ - 输入均为整数 ### 样例说明 1 以 $K = 1$ 为例。在这种情况下，高桥君只要带上护身符 $2$，就可以击败 $5$ 只怪兽，达到最多击败怪兽数。冒险过程如下： - 对于 $i = 1$，高桥君带有护身符 $2$，免疫了第 $1$ 只怪兽的攻击，然后击败它。 - 对于 $i = 2$，没有带护身符 $1$，受到攻击，体力变为 $6$，然后击败怪兽。 - 对于 $i = 3$，带有护身符 $2$，免疫攻击，然后击败怪兽。 - 对于 $i = 4$，带有护身符 $2$，免疫攻击，然后击败怪兽。 - 对于 $i = 5$，没有带护身符 $1$，受到攻击，体力变为 $1$，然后击败怪兽。 - 对于 $i = 6$，没有带护身符 $3$，受到攻击，体力变为 $-8$，无法击败怪兽，冒险结束。 同理，$K = 0$ 时最多击败 $2$ 只怪兽，$K = 2$ 时带上护身符 $2, 3$ 能击败全部 $7$ 只怪兽，$K = 3$ 时带上护身符 $1, 2, 3$ 也能击败全部 $7$ 只怪兽。 由 ChatGPT 4.1 翻译