By doing A and doing B (I'm sure you understand that in order to parallel doing A, what goes here should also be an ing form), we had enough money to try a three-star Michelin restaurant. So, what that leaves us with are only options C and D since only these two begin with words that end in ing.
Now, it's all down to deciding which one of the two makes more sense. I'd say that having it stick makes no sense whatsoever. I'm not even sure what it would mean in this context. Where are you going to stick your budget to? What's that supposed to mean?
The phrase stick to something, on the other hand, is a well-known expression in English which basically means keep doing something and not deviating from the established course or plan. And that's the one you should have picked:
By having a budget and sticking to it (making sure that we didn't go overbudget by keeping spending it carefully), we had enough money to try a three-star Michelin restaurant.