103146: [Atcoder]ABC314 G - Amulets

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

问题描述

山洞里有N只怪兽：怪兽1，怪兽2，$\ldots$，怪兽N。每只怪兽有一个正整数的攻击力和一个由1到M（包括1和M）之间的整数表示的类型。 具体来说，对于$i = 1, 2, \ldots, N$，怪兽$i$的攻击力和类型分别是$A_i$和$B_i$。

高桥同学将带着他的生命值为$H$和M种护符之一：护符1，护符2，$\ldots$，护符M在这个山洞里冒险。

在冒险过程中，高桥同学按照以下步骤进行（只要他的生命值不降为0或以下）：$i = 1, 2, \ldots, N$。

• 如果高桥同学没有携带护符$B_i$，怪兽$i$会攻击他并使他的生命值减少$A_i$。
• 然后，
  • 如果他的生命值大于0，他将击败怪兽$i$；
  • 否则，他在没有击败怪兽$i$的情况下死亡并结束冒险。

为每个$K = 0, 1, \ldots, M$独立解决以下问题。

找出高桥同学在选择带M个护符中的K个进行冒险时可以击败的最大数量的怪兽。

约束条件保证了对于每个$i = 1, 2, \ldots, M$，都有至少一只类型为$i$的怪兽。

约束条件

• $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$，令$X_i$为高桥同学在选择带M个护符中的K个进行冒险时可以击败的最大数量的怪兽。 按照以下格式打印$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$，他避免了怪兽1的攻击，因为他有护符2。然后，他击败了怪兽1。
• 对于$i = 2$，他承受了怪兽2的攻击，他的生命值降为6，因为他没有护符1。然后，他击败了怪兽2。
• 对于$i = 3$，他避免了怪兽3的攻击，因为他有护符2。然后，他击败了怪兽3。
• 对于$i = 4$，他避免了怪兽4的攻击，因为他有护符2。然后，他击败了怪兽4。
• 对于$i = 5$，他承受了怪兽5的攻击，他的生命值降为1，因为他没有护符1。然后，他击败了怪兽5。
• 对于$i = 6$，他承受了怪兽6的攻击，他的生命值降为-8，因为他没有护符3。然后，他在没有击败怪兽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