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?