DP を考えます。

\(dp[h][m]:=(\) 体力が \(h\) 、魔力が \(m\) のときに倒せるモンスターの数の最大値 \()\) とします。

\(t=dp[h][m]\) として以下のような遷移を考えます。（ 説明の都合上 \(A,B\) を 0-indexed として考えます。）

• \(dp[h+1][m]\gets \max(dp[h+1][m],t)\)
• \(dp[h][m+1]\gets \max(dp[h][m+1],t)\)
• \(t< N\) ならば
  • \(dp[h+A_t][m]\gets \max(dp[h+A_t][m],t+1)\)
  • \(dp[h][m+B_t]\gets \max(dp[h][m+B_t],t+1)\)

\((h,m)\) の昇順に DP を行うことで、答えは \(dp[H][M]\) となります。

DP の遷移は \(O(1)\) なので、DP の計算量は \(O(HM)\) 、よって全体の計算量は \(O(HM+N)\) となります。（ \(N\leq2\times 10^5\) でもこの問題を解くことができます。）

• 実装例 (C++ , 85 ms)
• 実装例 (Python , 425 ms)