It is over 30 minutes to write the algorithm based on the idea using dynamic programming. By going through the whiteboard testing, it took me two steps to come out the code passing all testing cases. First I wrote code to make sure that the value was correct, and then I change the code based on TED principle.
C# code is here.
I wrote two blogs about the algorithm, the first one is written in March 21, 2016. . The second one is here written in July 24, 2015.