Recently Lint want to buy some machines. His goal is to make as much money as possible in some days. During this period you will be able to buy and sell machines and operate them for profit while Lint owns them. Due to space restrictions, Lint can own at most one machine at a time.
There will be several machines for sale. Lint already knows the price Pi and the availability day Di for each machines Mi. Note that if he does not buy machine Mi on day Di, then somebody else will buy it and it will not be available later. Needless to say, Lint cannot buy a machine if he has less money than the price of the machine.
If Lint buy a machine Mi on day Di, then he can operate it starting on day Di + 1. Each day that the machine operates, it produces a profit of Gi dollars.
Lint may decide to sell a machine to reclaim a part of its purchase price any day after he’ve bought it. Each machine has a resale price Ri for which it may be resold to the market. He cannot operate a machine on the day that you sell it, but he may sell a machine and use the proceeds to buy a new machine on the same day.
Once the period ends, Lint will sell any machine that it still owns. Can you help Lint to maximize the amount of money that he makes during these days.