If you're not in a rush, get yourself an adapter or two and keep an eye on the charity shops. You're more likely to come across m42 than any other mount in my experience, and there are very few lenses not worth a couple of quid to try. I've a few rather battered lenses I've picked up for next to nothing that still produce an "interesting" image despite cleaning marks, filter thread dings and even light scratches.
I've picked up very clean and tidy lenses for as little as £3.75 from charity shops that are very usable. Some of the older, cheaper uncoated lenses have quite a bit of character - they won't win awards from pixel peepers but they might take an image that's popular. Occasionally you'll find a good bargain - I've found a CZJ Flektogon 35/2.4 for £5 in perfect condition (you'd pay £100+ on eBay) but missing the rear cap. Just watch in case the front/rear caps are missing - check the exposed elements for damage. Light scratches or cleaning marks won't make much of a difference and if the lens if only a couple of quid it might still be worth trying.