AT_abc314_g [ABC314G] Amulets

[problemUrl]: https://atcoder.jp/contests/abc314/tasks/abc314_g 洞窟に、モンスター $ 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 $ 体以上いることが、制約として保証されます。

入力は以下の形式で標準入力から与えられる。 > $ 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\ \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 $ が成り立つ - 入力はすべて整数 ### Sample Explanation 1 $ 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 $ 体のモンスター全てを倒すことができます。