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