G - Amulets Editorial /

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