Problem H
Vending Machine
Sleazy Bob has happened upon a vending machine. After watching enough people buy tasty snacks, Bob has realized that the vending machine is broken!
Here’s what Sleazy Bob observes:
-
A person tries to buy a snack
-
The vending machine then checks to see if there are any left of that snack
-
If there are any left, the machine charges the person for that snack
-
If the machine successfully charges the person, it then gives the person a different snack! Possibly no snack at all, if the machine is out of the different snack!
Sleazy Bob notices that, although the machine is broken, it
is at least consistent. Whenever a customer buys a snack from
position
Now, Bob wants to make a profit from the machine. He wants
to buy some snacks from the machine, and then turn around and
sell the snacks he gets for the market price of the snack. This
may be different from the vending price. If a cheap snack is at
Input
Each input will consist of a single test case. Note that
your program may be run multiple times on different inputs.
Each input begins with a line with a single integer
-
( ) is the value of . That is, it is the position from which the machine will vend when Bob buys from this position -
( ) is the price Bob must pay to buy from this position -
( ) is the market price of the snack at this position -
( ) is the number of snacks at this position
Output
Output a single line with a single integer, indicating the maximum profit Sleazy Bob can get from his nefarious abuse of the broken vending machine.
Sample Input 1 | Sample Output 1 |
---|---|
3 1 2 3 1 2 3 4 1 3 4 5 1 |
3 |
Sample Input 2 | Sample Output 2 |
---|---|
3 2 2 3 8 3 1 5 6 1 9 4 7 |
39 |
Sample Input 3 | Sample Output 3 |
---|---|
5 5 9 2 2 1 1 7 4 2 3 6 3 2 2 9 6 1 4 5 1 |
22 |