Do a binary search on answer.

Now, how do we check, whether it is possible to take X extensions in order to satisfy the problems condition?

Obviously, we'll consider only taking the greatest X extensions. Use Meet-In-The-Middle. Divide the greatest X extensions into two same-sized multisets A and B (the way you divide doesn't matter).

For each multiset count the following value — max_a[val] is the maximum product of all extentions you spend on extending the first side, while all other extensions are spend on the second side (we are only considering extensions in set A). We can brute forcing all the masks in A. Calculate max_b[] in the same way. Use map <  >  to store this data.

Now let's iterate over max_a[]. Consider having max_a[p] = q. Now we have to check, whether it is possible to take r extensions for the first side and s extensions for the second size (from the multiset B), so that a·p·r ≥ x and b·q·s ≥ y. We check this by doing a binary search over a max_b[].

So the overall complexity is — (which is actually faster than it sounds, because we don't consider MAX_ANS elements on every binary search step).

I guess, that this solution is not intented...