Hardest Problem Ever

Limits 5s, 1.0 GB

Prof.Dr.DP is very famous professor. He is expert (actually legendary grandmaster) in Dynamic Programming. Rinku is greedy girl. She always prefers greedy choices. She has recently learned Dynamic Programming from her programming teacher Prof.Dr.DP. He told her that whenever you have to minimize cost or maximize profit given condition that you have several choices for each time of selection, then dynamic programming can easily be applied there. So, they know that Dynamic programming basically useful for optimization problems. Now Prof.Dr.DP wants to test Rinku’s depth of knowledge in Dynamic Programming. So, He has given her a task. The task was as follows:

This is a companion discussion topic for the original entry at https://toph.co/p/hardest-problem-ever