Consider there is a city with $ n$ residents who are in need of internet and there are $ m$ internet providers in the city. Here in the city every resident needs internet and every resident knows what providers are available to him. Formally let resident $ i$ has list of providers $ a_i$ . Also each provider has a maximum number of connections he can give, that is, provider $ i$ can have at max $ k_i$ connections. Find the optimal way of providing internet so that the number of residents having internet is maximum.
My thoughts on the question is that this question looks like a derivative of knack-pack problem with constraints, which suggests dynamic programing but i am unable to find the states. Could anyone help me?