408696: GYM103264 E Преобразование выражения

E. Преобразование выраженияограничение по времени на тест2 секундыограничение по памяти на тест256 мегабайтвводстандартный вводвыводстандартный вывод

Вася обучает свою младшую сестру Машу сложению целых чисел. Вася уже написал некоторое корректное выражение и хочет предложить Маше посчитать значение этого выражения, то есть найти сумму записанных чисел. Выражение считается корректным, если выполнены следующие условия:

• выражение содержит одно или несколько целых неотрицательных чисел, разделенных знаком '+' (без кавычек)
• числа не содержат ведущих нулей (однако, числа, равные $$$0$$$, допустимы)
• каждый знак '+' находится между двумя числами

Когда всё выражение уже было готово, Вася вспомнил, что Маша может не знать достаточно больших чисел, чтобы найти сумму. Васе известно, что Маша знает целые числа от $$$0$$$ до $$$N$$$ включительно, соответственно, и сумма чисел в выражении должна не превосходить $$$N$$$. У Васи еще есть время, чтобы поменять не более $$$K$$$ символов в выражении (можно заменять любой символ на цифру или знак '+'), при этом выражение должно остаться корректным, а сумма получившихся чисел должна быть не более $$$N$$$. Кроме того, Вася хочет упростить задачу для сестры, поэтому он будет пытаться сделать так, чтобы слагаемые в выражении были как можно меньше, а именно — максимальное слагаемое в выражении должно быть минимально возможным. Помогите найти Васи оптимальное выражение, удовлетворяющее этим условиям.

Входные данные

Первая строка содержит три целых числа — $$$L$$$, $$$N$$$, $$$K$$$ — количество символов в исходном выражении, максимальное число, которое знает Маша, и максимально допустимое количество замен соответственно ($$$1 \leq L \leq 300$$$, $$$0 \leq N \leq 10^{9}$$$, $$$0 \leq K \leq L$$$). Во второй строке содержится исходное выражение, записанное Васей. Гарантируется, что выражение является корректным и содержит ровно $$$L$$$ символов (цифр и знаков '+').

Выходные данные

Если не существует преобразования выражения, удовлетворяющего всем условиям, нужно вывести -1 (см. пример 2). Если допустимые преобразования существуют, нужно вывести преобразованное выражение, в котором максимальное слагаемое будет как можно меньше. Выведенное выражение должно быть корректным.

Если существует несколько таких выражений, можно вывести любое из них (см. пример 3). Обратите внимание, что Васе не обязательно использовать все $$$K$$$ замен (см. пример 4).

Система оценки

Тесты, для которых выполняется $$$L \leq 16$$$, в сумме оцениваются в $$$40$$$ баллов.

ПримерыВходные данные

8 60 1
123+45+6

Выходные данные

1+3+45+6

Входные данные

5 20 1
21+12

Выходные данные

-1

Входные данные

5 10 2
4+4+4

Выходные данные

0+0+4

Входные данные

5 100 2
4+4+4

Выходные данные

4+4+4