题目描述

在洞窟中，有 $N$ 只怪兽，分别编号为 $1,2,\ldots,N$。第 $i$ 只怪兽有两个属性：

• 攻击力为 $A_i$
• 类型为 $B_i$，其中 $1 \le B_i \le M$

高桥君将从 $M$ 个护身符（编号也为 $1,2,\ldots,M$）中选择若干个带上，并以体力 $H$ 的状态进入洞窟。

接下来，他会按顺序依次遇到第 $1,2,\ldots,N$ 只怪兽。对于每只怪兽，执行下面的过程：

1. 如果高桥君没有带上类型为 $B_i$ 的护身符，那么他会受到这只怪兽的攻击，体力减少 $A_i$。
2. 如果此时体力仍然 大于 $0$，那么他就能击败这只怪兽，继续前进。
3. 如果体力变成 $0$ 或以下，那么他无法击败这只怪兽，冒险立即结束。

对于每个 $K=0,1,2,\ldots,M$，请分别独立回答下面的问题：

当高桥君从 $M$ 个护身符中恰好选择 $K$ 个带上时，他最多能击败多少只怪兽？

另外，保证每一种类型 $1,2,\ldots,M$ 都至少出现过一次。

输入格式

输入格式如下：

N M H
A_1 B_1
A_2 B_2
\cdots
A_N B_N

输出格式

设 $X_K$ 表示当选择 $K$ 个护身符时最多能击败的怪兽数。

请输出：

X_0 X_1 \cdots 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

输入样例 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 \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$，至少存在一只怪兽的类型为 $i$