In the latest update of the computer game "Totally Space!" it became possible to order spaceships. Each ship is characterized by its carrying capacity. Terminal
order shows two numbers: the number of already ordered spaceships
x and the initial carrying capacity of the ships
y. You also have
k experience points to spend
in the following way:
- Order a new ship with a capacity of
y. Operation cost: 1 experience point.
- Increase by 1 the carrying capacity of all ships already ordered at this point in time. Operation cost: 1 experience point.
You want to spend all
k experience points and you are wondering what is the maximum weight of cargo that can be transported using all the ordered ships.
In addition, you, as a frequent visitor to the game «Totally Space!», will encounter this problem more than once, so you are invited to solve it for four different situations.
| Situation number |
x |
y |
k |
| 1 |
1 |
1 |
2 |
| 2 |
3 |
4 |
4 |
| 3 |
6 |
6 |
7 |
| 4 |
2 |
8 |
8 |
The answer to this problem is four integers separated by a space: the maximum weight of the transported cargo in the first, second, third and fourth situations, respectively.
If you can't give an answer for a situation, write down any number as the answer for this situation.
Note
Let's look at an example. If the number of already ordered ships is 2, and their carrying capacity is 1, you have 2 experience points available. Then one of the best options is the following:
increase the number of ordered ships by 1 and spend one experience point, and then increase the carrying capacity of all ordered ships by 1 by spending another experience point. So
the maximum mass of cargo carried by these ships will be equal to 6 conventional units.