← 返回题目列表

Codeforces · 2011/C

C. 拆分表达式

中文机器翻译题面 查看原题

给您一个字符串 $$$s$$$,其形式为<数字块>+<数字块>+...+<数字块>。每个数字块至少由 $$$2$$$ 和最多 $$$13$$$ 数字组成;每个数字都是从 $$$1$$$ 到 $$$9$$$。

您必须将此字符串拆分为 <integer>+<integer> 形式的表达式。每个表达式必须是给定字符串的连续部分,并且给定字符串的每个字符必须恰好属于一个表达式。例如,如果您有字符串 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,因为第一部分包含两个 + 号。

在所有允许的分割字符串的方法中,找到一种能够最大化您获得的所有表达式的结果之和的方法,并打印该总和。

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 测试用例的数量。

每个测试用例由一行组成,其中包含字符串 $$$s$$$ ($$$5 \le |s| \le 1000$$$),其形式为<数字块>+<数字块>+...+<数字块>。该字符串至少包含一个“+”号。每个数字块至少由 $$$2$$$ 和最多 $$$13$$$ 数字组成;每个数字都是从 $$$1$$$ 到 $$$9$$$。

输出

对于每个测试用例,打印一个整数 - 分割字符串后得到的所有表达式结果的最大可能总和。

示例

输入 #1

3
123+456+789+555
13+37
9999999999999+1111111111111+9999999999999

输出 #1

834
50
20111111111110

注意

在示例的第一个测试用例中,您应该将字符串拆分为表达式 123+4、56+7 和 89+555。这些表达式的结果之和为 $$$834$$$。

在示例的第二个测试用例中,给定的字符串已经是有效的表达式,无法进一步拆分。