Dungeon

The Important Split

There are two completely different monster types:

• If $c_i>0$, the sword comes back with damage $\max(x,c_i)$. The sword count does not decrease, and the damage does not decrease.
• If $c_i=0$, the sword disappears. No upgrade, no refund, no nothing.

That second type is a trap if you do it early. Since a $c_i=0$ monster never helps future fights, we can always move all those fights to the end. Keeping extra swords around during the upgrade phase can only help.

So the plan is:

1. Kill as many $c_i>0$ monsters as possible, upgrading swords optimally.
2. Then spend swords on $c_i=0$ monsters.

One subtle point: $c_i>0$ does not mean the sword necessarily gets stronger. If $c_i<x$, the sword stays at $x$. But it still comes back, and that is the part that matters.

Greedy For Returning-Sword Monsters

Consider only monsters with $c_i>0$.

Sort them by increasing required life $b_i$.

For each monster, we want some sword with damage at least $b_i$. Among all valid swords, choose the weakest one.

Why weakest?

Suppose two eligible swords have damages $x \le y$. If we use $x$, the pair becomes:

$(\max(x,c_i), y)$

If we use $y$, the pair becomes:

$(x, \max(y,c_i))$

Using the weaker sword is never worse. If $c_i$ is small, nothing important changes. If $c_i$ is medium, the weak sword gets upgraded while the strong sword stays available. If $c_i$ is huge, upgrading the weak sword is obviously better because the strong sword remains strong too.

So the correct move is: use the weakest sword that can kill the monster.

A multiset gives exactly this with lower_bound(b_i).

If no sword can kill the current positive monster, then no later positive monster can be newly unlocked by it, because we sorted by $b_i$ and later requirements are at least as large. So the greedy process is done for positive monsters.

Each successful positive fight adds $1$ to the answer and replaces sword damage $x$ by $\max(x,c_i)$.

Then Spend The Swords

Now handle monsters with $c_i=0$.

These consume swords, so this is just matching swords to requirements. Sort these monsters by increasing $b_i$, and for each one use the weakest sword that can kill it.

Again, this is the standard greedy: do the easiest remaining monster with the smallest usable sword, saving bigger swords for bigger problems.

Algorithm

For each test case:

1. Put all initial sword damages into a multiset.
2. Split monsters into:
   • positive monsters: $(b_i,c_i)$ where $c_i>0$
   • consuming monsters: $b_i$ where $c_i=0$
3. Sort positive monsters by $b_i$.
4. For each positive monster:
   • find the weakest sword $x \ge b_i$
   • if none exists, stop this phase
   • erase $x$, insert $\max(x,c_i)$
   • increment answer
5. Sort consuming monsters by $b_i$.
6. For each consuming monster:
   • find the weakest sword $x \ge b_i$
   • if none exists, stop
   • erase $x$
   • increment answer

Complexity is $O((n+m)\log n)$ per test case, which fits easily because the total input size is $2\cdot 10^5$.