By always defending when attacked, \(\max(N+B-A,0)\) monsters will survive.

Let \(C_i\) be the total number of times monster \(i\) is attacked. If the sum of the \(d\) smallest \(C_i\)’s is at most \(B\), you can protect \(d\) monsters (by defending just those \(d\) monsters).

The above two strategies give a lower bound for the answer, and this is actually sufficient. The proof can be done by induction.

Another way of thinking is that the fewer times an attack actually occurs, the better. Assuming that you use up all \(B\) defenses, if the number of times an attack occurs is \(S\), the number of monsters that will survive in the end is \(N+B-S\), so the smaller \(S\) is, the better. The hero will act to maximize \(S\), but this simply settles down to attacking as long as he has MP. The case \(S = A\) corresponds to the first strategy, and the case \(S<A\) corresponds to the second strategy. The monsters that survived in the end are those that were attacked \(C_i\) times, so they required \(C_i\) defenses. Therefore, it is optimal to protect the monsters with the smallest \(C_i\)’s.

All computations can be done in \(O(N+M)\) time.

Sample Implementation