

Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 575 点
問題文
洞窟に、モンスター 1 、モンスター 2 、\ldots 、モンスター N の N 体のモンスターがおり、各モンスターには正整数の攻撃力と、1 以上 M 以下の整数で表されるタイプが定められています。 具体的には、i = 1, 2, \ldots, N について、モンスター i の攻撃力は A_i でタイプは B_i です。
高橋君はお守り 1 、お守り 2 、\ldots 、お守り M の M 個のお守りのうちのいくつかを持って、体力が H の状態でこの洞窟に冒険に出かけます。
冒険では高橋君は(体力が 0 以下になって力尽きない限り)i = 1, 2, \ldots, N の順に下記の手順を行います。
- もし高橋君がお守り B_i を冒険に持ってきていないなら、高橋君はモンスター i の攻撃を受け、高橋君の体力が A_i だけ減少する。
- その後の時点での高橋君の体力が、
- 0 より大きいならば、高橋君はモンスター i を倒す。
- 0 以下ならば、高橋君はモンスター i を倒せずに力尽きて冒険を終了する。
K = 0, 1, \ldots, M のそれぞれの場合について独立に、下記の問題を解いてください。
高橋君が全 M 個のお守りの中から K 個を選んで冒険に持っていくときの、高橋君が倒すモンスターの数としてあり得る最大値を求めよ。
なお、任意の i = 1, 2, \ldots, M について、タイプが i であるモンスターが必ず 1 体以上いることが、制約として保証されます。
制約
- 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 について、K = i の場合の高橋君が倒すモンスターの数の最大値を X_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 について、高橋君はお守り 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 体のモンスター全てを倒すことができます。
入力例 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
Score : 575 points
Problem Statement
There are N monsters in a cave: monster 1, monster 2, \ldots, monster N. Each monster has a positive integer attack power and a type represented by an integer between 1 and M, inclusive. Specifically, for i = 1, 2, \ldots, N, the attack power and type of monster i are A_i and B_i, respectively.
Takahashi will go on an adventure in this cave with a health of H and some of the M amulets: amulet 1, amulet 2, \ldots, amulet M.
In the adventure, Takahashi performs the following steps for i = 1, 2, \ldots, N in this order (as long as his health does not drop to 0 or below).
- If Takahashi has not brought amulet B_i with him, monster i will attack him and decrease his health by A_i.
- Then,
- if his health is greater than 0, he defeats monster i;
- otherwise, he dies without defeating monster i and ends his adventure.
Solve the following problem for each K = 0, 1, \ldots, M independently.
Find the maximum number of monsters that Takahashi can defeat when choosing K of the M amulets to bring on the adventure.
The constraints guarantee that there is at least one monster of type i for each i = 1, 2, \ldots, M.
Constraints
- 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
- For each 1 \leq i \leq M, there is 1 \leq j \leq N such that B_j = i.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M H A_1 B_1 A_2 B_2 \vdots A_N B_N
Output
For each i = 0, 1, 2, \ldots, M, let X_i be the maximum number of monsters that Takahashi can defeat when K = i. Print X_0, X_1, \ldots, X_M separated by spaces in the following format:
X_0 X_1 \ldots X_M
Sample Input 1
7 3 7 3 2 1 1 4 2 1 2 5 1 9 3 2 3
Sample Output 1
2 5 7 7
Consider the case K = 1. Here, Takahashi can bring amulet 2 to defeat the maximum possible number of monsters, which is 5. The adventure proceeds as follows.
- For i = 1, he avoids the attack of monster 1 since he has amulet 2. Then, he defeats monster 1.
- For i = 2, he takes the attack of monster 2 and his health becomes 6 since he does not have amulet 1. Then, he defeats monster 2.
- For i = 3, he avoids the attack of monster 3 since he has amulet 2. Then, he defeats monster 3.
- For i = 4, he avoids the attack of monster 4 since he has amulet 2. Then, he defeats monster 4.
- For i = 5, he takes the attack of monster 5 and his health becomes 1 since he does not have amulet 1. Then, he defeats monster 5.
- For i = 6, he takes the attack of monster 6 and his health becomes -8 since he does not have amulet 3. Then, he dies without defeating monster 6 and ends his adventure.
Similarly, when K=0, he can defeat 2 monsters; when K=2, he can defeat all 7 monsters by bringing amulets 2 and 3; when K=3, he can defeat all 7 monsters by bringing amulets 1, 2, and 3.
Sample Input 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
Sample Output 2
8 12 15 15 15 15