Вам дана строка \(s\) длины \(n > 1\), состоящая из цифр от \(0\) до \(9\). Вы должны вставить в эту строку ровно \(n - 2\) знака \(+\) (сложение) или \(\times\) (умножение), чтобы получилось корректное арифметическое выражение.
В этой задаче нельзя, чтобы знаки были перед первым или после последнего символа строки \(s\), а также не может быть записано два каких-либо знака подряд. Также обращаем ваше внимание на то, что вы не меняете порядок цифр в строке. Рассмотрим \(s = 987009\):
- Из этой строки можно получить следующие математические выражения: \(9 \times 8 + 70 \times 0 + 9 = 81\), \(98 \times 7 \times 0 + 0 \times 9 = 0\), \(9 + 8 + 7 + 0 + 09 = 9 + 8 + 7 + 0 + 9 = 33\). Обратите внимание, что число \(09\) считается корректным и преобразуется просто в \(9\).
- Из этой строки нельзя получить следующие математические выражения: \(+9 \times 8 \times 70 + 09\) (знаки должны стоять только между цифрами), \(98 \times 70 + 0 + 9\) (так как цифр \(6\), должно быть ровно \(4\) знака).
Результат математического выражения считается по правилам математики — сначала выполняются все операции умножения, затем сложения. Вам нужно найти минимальный результат, который можно получить, вставив в данную строку \(s\) ровно \(n - 2\) знака сложения или умножения.
Выходные данные
Для каждого набора входных данных выведите минимальный результат математического выражения, который можно получить, вставив в данную строку ровно \(n - 2\) знака сложения или умножения.
Примечание
В первых четырех наборах входных данных мы не можем добавлять знаки, поэтому ответом будет исходное число.
В пятом наборе входных данных оптимальный ответ выглядит следующим образом \(9 \times 01 = 9 \times 1 = 9\).
В шестом наборе входных данных оптимальный ответ выглядит следующим образом \(1 \times 01 = 1 \times 1 = 1\).
В седьмом наборе входных данных оптимальный ответ выглядит следующим образом \(2 + 3 + 3 + 11 = 19\).
В восьмом наборе входных данных один из оптимальных ответов выглядит следующим образом \(98 \times 7 \times 0 + 0 \times 9 = 0\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
18
2
10
2
74
2
00
2
01
3
901
3
101
5
23311
6
987009
7
1111111
20
99999999999999999999
20
00000000000000000000
4
0212
18
057235283621345395
4
1112
20
19811678487321784121
4
1121
4
2221
3
011
|
10
74
0
1
9
1
19
0
11
261
0
0
0
12
93
12
24
0
|