分数: 575 点
问题陈述
有 N 山洞里的怪物:怪物 1,怪物 2, \ldots,怪物 N。每个怪物都有一个正整数 攻击力 和 黑板上写着 类型 由介于之间的整数表示 1 和 M,包括在内。 具体来说,对于 i = 1, 2, \ldots, N,怪物的攻击力和类型 i 是 A_i 和 B_i。
高桥将与一个人一起在这个洞穴里冒险 健康 of H 和一些 M 护身符:护身符 1,护身符 2, \ldots,护身符 M.
在冒险中,高桥执行以下步骤: i = 1, 2, \ldots, N 按此顺序(只要他的生命值不下降到 0 或以下)。
- 如果高桥没有带护身符 B_i 和他一起,怪物 i 会攻击他并降低他的生命值 A_i.
- 然后,
- 如果他的生命值大于 0,他打败了怪物 i;
- 否则,他在没有击败怪物的情况下就死了 i 并结束了他的冒险。
解决以下每个问题 K = 0, 1, \ldots, M 独立。
找出高桥选择时可以击败的最大怪物数量 K 的 M 带来冒险的护身符。
约束保证至少有一个类型的怪物 i 对于每个 i = 1, 2, \ldots, 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.
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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
7 3 7 3 2 1 1 4 2 1 2 5 1 9 3 2 3
示例输出 1
2 5 7 7
考虑这种情况 K = 1。在这里,高桥可以带护身符 2 击败尽可能多的怪物,即 5。 冒险的进行如下。
- 对于 i = 1,他躲避了怪物的攻击 1 因为他有护身符 2。然后,他打败了怪物 1.
- 对于 i = 2,他受到怪物的攻击 2 他的健康状况变得 6 因为他没有护身符 1。然后,他打败了怪物 2.
- 对于 i = 3,他躲避了怪物的攻击 3 因为他有护身符 2。然后,他打败了怪物 3.
- 对于 i = 4,他躲避了怪物的攻击 4 因为他有护身符 2。然后,他打败了怪物 4.
- 对于 i = 5,他受到怪物的攻击 5 他的健康状况变得 1 因为他没有护身符 1。然后,他打败了怪物 5.
- 对于 i = 6,他受到怪物的攻击 6 他的健康状况变得 -8 因为他没有护身符 3。然后,他没有打败怪物就死了 6 并结束了他的冒险。
同样,当 K=0,他可以击败 2 怪物;当 K=2,他可以打败一切 7 怪物通过携带护身符 2 和 3;当 K=3,他可以打败一切 7 怪物通过携带护身符 1, 2,和 3.
示例输入 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