Score : $575$ points

问题描述

在一个洞穴中有 $N$ 只怪兽：怪兽1、怪兽2，……，怪兽$N$。每只怪兽都有一个正整数的攻击力和一个用1到$M$之间的整数表示的类型。具体来说，对于$i=1,2,\ldots,N$，怪兽$i$的攻击力和类型分别为$A_i$和$B_i$。

高桥将以生命值为$H$并携带一些从$M$个护符中挑选出的护符（护符1、护符2，……，护符$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$的怪兽。

以上为通义千问 qwen-max 翻译，仅供参考。

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

update @ 2024/3/10 08:59:43