Лёша играет в недавно вышедшую новую версию легендарной игры hacknet. В этой версии был добавлен механизм навыков. Теперь каждый игровой персонаж обладает ровно n навыками. Каждый навык представляется одним неотрицательным целым числом ai — текущим уровнем навыка. Все навыки имеют одинаковый максимальный уровень A.
Одновременно с навыками был введён всеобщий рейтинг всех игроков. Игроки ранжируются по так называемой Силе. Сила игрока считается как сумма следующих величин:
- Количество навыков, которыми персонаж владеет в совершенстве (т.е. таких, что ai = A), умноженное на коэффициент cf.
- Минимальный текущий уровень среди всех навыков (min ai), умноженный на коэффициент cm.
Сейчас у Лёши есть m хакнетианских денежных единиц, которые он готов потратить. Каждая денежная единица позволяет увеличить текущий уровень любого навыка на 1 (если его уровень еще не максимален). Помогите ему потратить деньги таким образом, чтобы достичь как можно большего уровня Силы.
Выходные данные
Сначала выведите максимальное значение Cилы, которое может получить персонаж.
Затем выведите n целых чисел — a'i (ai ≤ a'i ≤ A), уровни навыков, до которых следует развиться, чтобы достичь указанного значения Силы, при этом используя не более m денежных единиц. Если правильных ответов несколько — выведите любой.
Примечание
В первом тесте оптимальной стратегией является повышение второго навыка до его максимума, а остальных — на единицу.
Во втором тесте нужно увеличить уровни всех навыков до максимума.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 10 1 5
1 3 1
|
12
2 5 2
|
|
2
|
3 5 10 1 339
1 3 1
|
35
5 5 5
|