Statement

After William's modest success at the Pay That Box! game show, everybody in the OIS staff tried to get selected for it as well… and Edoardo made it! Since he doesn't like to take blind decisions, he also managed to hack into the show servers and downloaded the list of boxes that he will encounter. As you already know, Edoardo will \underlinechoose a starting budget of M euros, then open a sequence of N boxes one at a time, from i=0 to N-1. Each box contains a prize, \underlinewhich is worth V_i euros for Edoardo, and he can either get it using P_i euros from his budget, or he can pass it gaining a compensation of C_i euros. At the end of the show, Edoardo will evaluate his gain G as the sum of values V_i of the prizes bought plus the (possibly negative) money overall gained in the process. Of course, he wants to have the highest gain G possible, using the smallest budget M allowing him to get it. Help him get the best deal!