my problem is, I know my travel dates (mid-August) and I know my budget, but still not sure where to go. Unfortunately Kayak searches (including this very cool hack) are useless at solving that.

P.S. ITA Software Matrix is good at this if you have a list of places, but not for random destinations.