{"problem":{"name":"Amulets","description":{"content":"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$, in","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc314_g"},"statements":[{"statement_type":"Markdown","content":"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.\nTakahashi 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$.\nIn 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).\n\n*   If Takahashi has not brought amulet $B_i$ with him, monster $i$ will attack him and decrease his health by $A_i$.\n*   Then,\n    *   if his health is greater than $0$, he defeats monster $i$;\n    *   otherwise, he dies without defeating monster $i$ and ends his adventure.\n\nSolve the following problem for each $K = 0, 1, \\ldots, M$ independently.\n\n> Find the maximum number of monsters that Takahashi can defeat when choosing $K$ of the $M$ amulets to bring on the adventure.\n\nThe constraints guarantee that there is at least one monster of type $i$ for each $i = 1, 2, \\ldots, M$.\n\n## Constraints\n\n*   $1 \\leq M \\leq N \\leq 3 \\times 10^5$\n*   $1 \\leq H \\leq 10^9$\n*   $1 \\leq A_i \\leq 10^9$\n*   $1 \\leq B_i \\leq M$\n*   For each $1 \\leq i \\leq M$, there is $1 \\leq j \\leq N$ such that $B_j = i$.\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $H$\n$A_1$ $B_1$\n$A_2$ $B_2$\n$\\vdots$\n$A_N$ $B_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc314_g","tags":[],"sample_group":[["7 3 7\n3 2\n1 1\n4 2\n1 2\n5 1\n9 3\n2 3","2 5 7 7\n\nConsider 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.\n\n*   For $i = 1$, he avoids the attack of monster $1$ since he has amulet $2$. Then, he defeats monster $1$.\n*   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$.\n*   For $i = 3$, he avoids the attack of monster $3$ since he has amulet $2$. Then, he defeats monster $3$.\n*   For $i = 4$, he avoids the attack of monster $4$ since he has amulet $2$. Then, he defeats monster $4$.\n*   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$.\n*   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.\n\nSimilarly, 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$."],["15 5 400\n29 5\n27 4\n79 1\n27 2\n30 3\n4 1\n89 2\n88 3\n75 5\n3 1\n39 4\n12 1\n62 4\n38 2\n49 1","8 12 15 15 15 15"]],"created_at":"2026-03-03 11:01:14"}}