Codeforces 739E Gosha is Hunting - Problem Statement

You have $n$ Pokemon, $a$ Poke Balls, and $b$ Ultra Balls. Pokemon $i$ is caught with probability $p_i$ by Poke Ball, $u_i$ by Ultra Ball. You can use at most one of each ball type per Pokemon. Find the largest expected catches.

If you throw both balls at Pokemon $i$, the catch probability is $p_i + u_i - p_i \cdot u_i$ (at least one succeeds). The constraint is two-dimensional: exactly $a$ Poke Balls AND exactly $b$ Ultra Balls. Standard DP is $O(n \cdot a \cdot b)$, which is $O(n^3)$. Too slow.