Вам дана строка \(s\) вида <блок цифр>+<блок цифр>+...+<блок цифр>. Каждый блок цифр состоит из не менее \(2\) и не более \(13\) цифр; каждая цифра от \(1\) до \(9\).
Вам нужно разделить эту строку на выражения в форме <целое число>+<целое число>. Каждое полученное выражение должно быть непрерывной частью исходной строки, и каждый символ исходной строки должен быть включен ровно в одно выражение. Например, если у вас есть строка 123+456+789+555, то:
- вы можете разделить ее на 123+4, 56+7 и 89+555;
- вы не можете разделить ее на 123+456 и +789+555, так как вторая часть начинается с знака +;
- вы не можете разделить ее на 123+4, 56+7, 8 и 9+555, так как третья часть не содержит знака +;
- вы не можете разделить ее на 123+456+78 и 9+555, так как первая часть содержит два знака +.
Среди всех разрешенных способов разделить строку найдите тот, который максимизирует сумму результатов всех выражений, которые вы получите, и выведите эту сумму.
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальную возможную сумма результатов всех выражений, которые вы получите после разделения строки.
Примечание
В первом наборе входных данных примера вам следует разделить строку на выражения 123+4, 56+7 и 89+555. Сумма результатов этих выражений равна \(834\).
Во втором наборе входных данных примера данная строка уже является допустимым выражением и не может быть разделена дальше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
123+456+789+555
13+37
9999999999999+1111111111111+9999999999999
|
834
50
20111111111110
|