Well it depends. Do you want to use the 5000 in one month, or over a long period of time? What is your audience? Does your service appeal to all who see it or just a specific group? How much are you willing to spend per customer, and do you care about the quality of customers (Advertising in the low budget advertising section with the lowest price will get you a ton of host hoppers and people looking for a cheap way to send spam).
Is 5000 a significant amount to your company, do you have room to experiment? How have your past advertising experiences gone? Would you be happy to go with the magazines you've advertised in again?
You should analyze what exactly your looking for, then choose the best route, or go to an advertising firm and get their opinions.
As for great advertising ideas, I give advise but I keep those special things I come up with 🙂
