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

输入 #1

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

输出 #1

2 5 7 7

输入输出样例 #2

输入 #2

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

输出 #2

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$
• 输入均为整数

样例说明 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 翻译