I asked a guy from a PR firm about this at an event at my local University.
He said getting stories in local newspapers costs about £2000. National press (meaning in the UK, not the USA) costs more. But it costs way less than the $20k I thought it did.