В последнем обновлении компьютерной игры «Totally Space!» появилась возможность заказывать космические корабли. Каждый корабль характеризуется своей грузоподъемностью. Терминал
заказа показывает два числа: количество уже заказанных космических кораблей
x и начальную грузоподъемность кораблей
y. Также у вас есть
k очков опыта, которые вы можете израсходовать
следующим образом:
- Заказать новый корабль с грузоподъемностью
y. Стоимость операции: 1 очко опыта.
- Увеличить на 1 грузоподъемность всех кораблей, уже заказанных на данный момент времени. Стоимость операции: 1 очко опыта.
Вы захотели потратить все
k очков опыта, и вам стало интересно, какова же максимальная масса груза, которую можно перевезти, используя все заказанные корабли.
Кроме того, вы, как частый посетитель игры «Totally Space!», еще не раз столкнётесь с данной задачей, поэтому вам предлагается решить её для четырёх разных ситуаций.
| Номер ситуации |
x |
y |
k |
| 1 |
1 |
1 |
2 |
| 2 |
3 |
4 |
4 |
| 3 |
6 |
6 |
7 |
| 4 |
2 |
8 |
8 |
Ответом на данную задачу являются четыре целых числа, перечисленных через пробел: максимальная масса перевозимого груза в первой, второй, третьей и четвертой ситуациях соответственно.
Если вы не можете дать ответ для какой-то ситуации, запишите в качестве ответа для данной ситуации любое число.
Замечание
Рассмотрим пример. Пусть количество уже заказанных кораблей равно 2, и их грузоподъемность равна 1, вам доступно 2 очка опыта. Тогда один из оптимальных вариантов следующий:
увеличить количество заказанных кораблей на 1 и потратить одно очко опыта, а затем увеличить грузоподъемность всех заказанных кораблей на 1, потратив еще одно очко опыта. Таким образом,
максимальная масса груза, перевозимая данными кораблями, будет равна 6 условных единиц.