Split the Expression
Contest: Kotlin Heroes: Episode 11
Tags: *special

You are given a string $$$s$$$ of the form <block of digits>+<block of digits>+...+<block of digits>. Every block of digits consists of at least $$$2$$$ and at most $$$13$$$ digits; every digit is from $$$1$$$ to $$$9$$$.

You have to split this string into expressions of the form <integer>+<integer>. Every expression must be a contiguous part of the given string, and every character of the given string must belong to exactly one expression. For example, if you have a string 123+456+789+555, then:

- you are allowed to split it into 123+4, 56+7 and 89+555;
- you are not allowed to split it into 123+456 and +789+555, since the second part begins with a + sign;
- you are not allowed to split it into 123+4, 56+7, 8 and 9+555, since the third part does not contain a + sign;
- you are not allowed to split it into 123+456+78 and 9+555, since the first part contains two + signs.

Among all allowed ways to split the string, find one which maximizes the sum of results of all expressions you get, and print this sum.

Input format:
The first line contains one integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases.

Each test case consists of one line containing the string $$$s$$$ ($$$5 \le |s| \le 1000$$$) of the form <block of digits>+<block of digits>+...+<block of digits>. The string contains at least one '+' sign. Every block of digits consists of at least $$$2$$$ and at most $$$13$$$ digits; every digit is from $$$1$$$ to $$$9$$$.

Output format:
For each test case, print one integer — the maximum possible sum of results of all expressions you get after splitting the string.

Constraints:
Time limit: 2.0 s
Memory limit: 512.0 MB

Note:
In the first test case of the example, you should split the string into expressions 123+4, 56+7 and 89+555. The sum of results of these expressions is $$$834$$$.

In the second test case of the example, the given string is already a valid expression and cannot be split any further.

Example input:
3
123+456+789+555
13+37
9999999999999+1111111111111+9999999999999

Example output:
834
50
20111111111110

Editorial:
This problem is much easier to implement in Kotlin than in, for example, C++.
First of all, since every expression contains one + sign, the number of expressions should be equal to the number of + signs. Furthermore, we can find the positions to split the given expression: in every block of digits except for the first and the last block, we need to choose a "cut" that leaves both parts of the block non-empty.
After we've chosen our "cut" positions, the sum of all expressions is just the sum of all integers we obtained. So, for every block (except for the first block and the last block), we have to split it so that the sum of two parts is the maximum possible. This can be done in two ways: either iterate on the position of the cut in a block, or check two options: make the left part a single digit, or the right part a single digit.
To split the given string into blocks of digits, you can use the method split("+"). The method toLong() will also be very helpful to convert blocks of digits into numbers (32-bit integers are not enough in this problem).