护身符

题目描述

洞穴中有 $N$ 只怪物，分别是怪物 $1$、怪物 $2$、$\ldots$、怪物 $N$。每只怪物都有一个正整数攻击力和一个介于 $1$ 到 $M$（含）之间的整数类型。 具体地，对于 $i = 1, 2, \ldots, N$，怪物 $i$ 的攻击力和类型分别为 $A_i$ 和 $B_i$。

高桥君将以 $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$ 独立地解决以下问题：

当高桥君选择携带 $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$

样例

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

2 5 7 7

考虑 $K = 1$ 的情况。此时，高桥君可以携带护身符 $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$ 只怪物。

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 \le M \le N \le 3 \times 10^5$
• $1 \le H \le 10^9$
• $1 \le A_i \le 10^9$
• $1 \le B_i \le M$
• 对于每个 $1 \le i \le M$，存在 $1 \le j \le N$ 使得 $B_j = i$。
• 输入均为整数。