This problem can be solved with DP (Dynamic Programming).

Let \(\mathrm{DP}[i][m]\) be the maximum health after defeating the first \(i\) monsters if the magic power at that point is \(m\). (If the magic power can never become \(m\) at that point, let it be \(-1\).)

Considering whether to use the magic or not, we obtain the following recurrence relations:

\(\mathrm{DP}[i][m]=\max(\mathrm{DP}[i-1][m]-A_i, \mathrm{DP}[i-1][m+B_i]).\)

This allows us to find \(\mathrm{DP}[i][*]\) from \(\mathrm{DP}[i-1][*]\). Beware of boundary conditions.

If \(\max_m\mathrm{DP}[i][m]\geq 0\), there is a way to defeat the first \(i\) monsters; otherwise, there is not.

The DP has \(O(NM)\) states, and each transition costs \(O(1)\) time, so the problem has been solved in a total of \(O(NM)\) time.

Another solution

\(\mathrm{DP}[i][h][m]\) denote whether defeating the first \(i\) monsters can result in health \(h\) and magic power \(m\).

This DP costs \(O(NHW)\) time, but with an ingenious implementation like using a bitset and a fast language, it will finish within the execution time limit.