R3D3 прошёл стажировку в MDCS, заработал достаточно денег и отправился отдыхать на далёкий-далёкий курорт. Там он принимал солнечные ванны, пил безалкогольные коктейли и ходил на концерты популярных местных групп. Слушая группу «Белые пуговицы» и их новый хит «Пекарь Дакан», он заметил девушку-робота и сразу понял, что это любовь его жизни. Ну, или по крайне мере, этого лета. В любом случае, R3D3 оказался слишком стеснительным чтобы подойти к ней первым, поэтому он решил написать ей любовное письмо. Однако и тут его поджидала проблема, поскольку в целях обеспечения безопасности и стабильности Межгалактическая Космическая Полиция проверяла всю почту, отправляемую в данной области. Поэтому R3D3 решил изобрести собственную кодировку для алфавита.
В алфавите R3D3 n букв, и он хочет закодировать каждую из них последовательностью из «0» и «1». При этом, чтобы облегчить расшифровку, он хочет чтобы кодировка любой буквы не являлась префиксом кодировки никакой другой буквы. Поскольку недавно Межгалактическая Космическая Коммуникационная Служба ввела налоги на новоизобретённые кодировки алфавитов, R3D3 придётся заплатит определённую сумму за каждый бит в его кодировку (посмотри комментарий к тесту из примера). Он слишком влюблён чтобы мыслить ясно, поэтому просит вас помочь ему.
Вам даны стоимости c0 и c1, определяющие плату за каждое использование «0» и «1» в кодировке R3D3. Требуется придумать кодировку минимальной стоимости, удовлетворяющую при этом требованию беспрефиксности, описанному выше.
Примечание
В примере в алфавите 4 буквы. Оптимальной кодировкой будет являться «00», «01», «10», «11». Всего использовано 4 нуля и 4 единицы, поэтому итоговая стоимость равна 4·1 + 4·2 = 12.