Creating managed solutions requires CDS database. Does that mean all solutions are Premium?

I am creating managed Solutions where all components in the solution are canvas apps and flows just using standard connectors. Since setting up a new solution in an environment requires a Common Data Store database to be created I was wondering if using solutions by default requires all users of the packaged apps/flows to be premium licensed? (Per app/per user plans). Today all our users are O365 E3.

Thanks for any tips!