Recently I was trying to solve this problem. Somewhere I had seen that the intended solution uses dp with broken profile. But I had a much simpler solution using MCMF. But the problem with this solution is that negative cycles are getting formed. Is there any way to handle negative cycles in MCMF ? I am not familiar with the MCMF algorithm, so it would be better if someone provides the implementation. Thanks in advance.