If we can find the number of amulets \(L_i\) required to defeat at least \(i\) monsters fast enough for all \(i = 0, 1, 2, \ldots, N\), the problem can be solved; because, once we find \(L = (L_0, L_1, \ldots, L_N)\), the answer for \(K = i\) is the minimum \(j\) with \(L_j \leq i\), which can be found with a binary search or sliding window technique on \(L\) fast enough.

Let us fix \(i\) and consider how to find \(L_i\). Here, instead of \(L_i\), we seek for \(M-L_i\), the maximum number of amulets that can be left unused to defeat at least \(i\) monsters.

For each type \(j = 1, 2, \ldots, M\), let \(C_j\) be the total attack power of the monsters \(1\) through \(i\) of type \(j\). Then, leaving amulet \(j\) means accepting a total damage of \(C_j\) from the monsters of type \(j\) before defeating monster \(i\). The total acceptable damage before defeating monster \(i\) is \(H-1\), and it is optimal to leave amulets \(j\) with smallest \(C_j\), so \(M - L_i\) equals

the number of amulets that can be taken when we repeatedly and greedily choose an amulets with the smallest \(C_j\) from the \(M\) amulets, while the sum of \(C_j\) is strictly less than \(H\).

Now that we have found how to find \(L_i\) for one \(i\), we now want to find \(L_i\) for all \(i\). Naively finding \(L_i\) for all \(i\) as described above costs a excessive computation time, so we have to device a smarter way. Here, note the following fact:

Increasing \(i\) by one modifies only \(C_{B_{i+1}}\) among \(C_1, C_2, \ldots, C_M\), so a constant number of elements in the sets of amulets \(S\) to be taken and \(T\) to be left as \(i\) increases by one.

Using this fact, one can manage \(S\) and \(T\) in data structures that supports addition, deletion, and retrieval of maximum/minimum values, such as balanced binary trees, so that increasing \(i\) requires only a small differential updates to obtain \(C,S\), and \(T\) for new \(i\) from those for old \(i\). This way, one can find \(L_i\) fast enough for all \(i = 0, 1, 2, \ldots, N\) by successively incrementing \(i\); hence, the problem can be solved in a total of \(O(M + N\log M)\) time.