It is a Norwegian streaming service that is supposed to have more than 23,000,000 songs (I have'nt counted), and they have a service that streams in CD quality.
At home I have a 70Gb download speed, so it is not a problem streaming this quality over the internet, and downloads are quite fast.
https://wimp.no/wweb/iwannarock/ (use Google translate)
As you can see the Premium service (AAC 320 KBPS) costs 99,- NOK a month, and the Hi-Fi service (16/44.1 FLAC) costs 199,- NOK a month.
That is approximately $16 and $32 a month (USD).
When I want to use offline playlists I just choose songs, albums or playlists that I want to use offline, and my iOS device starts the download.. once a month it needs to be connected to the internet though.. because the app needs to confirm that I am still a customer.
And to be clear.. I do not have ALL songs available locally..