この問題はDPにより解くことができます。

\(\mathrm{DP}[i][m]\) を、\(i\) 体目のモンスターまで倒した時点で魔力が \(m\) であるときの体力の最大値とします。（\(i\) 体目のモンスターまで倒した時点で魔力が \(m\) になることがなければ \(-1\) とする）

\(i\) 体目のモンスターに対して魔法を使うかどうかを考えることで

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

のような漸化式により \(\mathrm{DP}[i-1][*]\) から \(\mathrm{DP}[i][*]\) を求めることができます。境界条件などに注意しましょう。

\(\max_m\mathrm{DP}[i][m]\geq 0\) のとき \(i\) 体目のモンスターまで倒す方法が存在し、そうでないとき存在しません。

DP の状態数は \(O(NM)\) であり、遷移は \(O(1)\) なので、全体で \(O(NM)\) でこの問題が解けました。

別解

\(\mathrm{DP}[i][h][m]\) を、\(i\) 体目のモンスターまで倒した時点で体力が \(h\) 魔力が \(m\) の状態になることがあるかの真偽値とします。

このDPは \(O(NHW)\) 時間かかりますが、bitsetを用いるなどの実装上の工夫により、C++,PyPyなどの高速な言語であれば実行時間制限に間に合わせることができます。