But the budget I am thinking of is temporal rather than monetary. Prep is typically time-expensive for me. But I knew a DM once who ran an ~10 month campaign on about an hour of prep right before every session. Granted, it was somewhat railroady, but it was generally a pretty good game.
So how to prep efficiently for sandbox gaming? Strategies:
- Profile - figure out what parts of your prep process are slow, and focus on improving those. First step of optimizing slow software, but not something I've ever heard of people doing consciously for D&D prep. Maybe I will try this and post the results.
- Reduce - only prep things that are very likely to be useful in play
- Reuse - prefer to prep things that are going to be used multiple times  
- Randomize - prep tables which can be used to generate content quickly during play. This is sort of "preparing for the unknown"; you don't know what your players will do, but good tables speed up your response time (or at least help you stall) when you're drawing a blank.
- Automate - let Friend Computer do some of the heavy lifting, when it makes sense to spend the time to teach it. Good thing we have self-profiling data, right?