I have been stuck at this problem for quite a long time now. Can someone please provide a detailed solution. I know the trick to be used is broken profile dp, but after that I am in a dead end. Thanks in advance.