时空密文重排

题目描述

在一间被遗忘的时空研究所中，你发现了一台仍在运转的古老量子终端。屏幕上不断闪烁着一串奇怪的字符，由数字 1 到 9 和若干加号 + 组成。

研究所的日志提到：这串字符其实是一个 时空能量式，但被量子扰动打乱了顺序。只有将其重新排列成一个 完全合法且能量最小 的表达式，才能降低终端的负荷，阻止它因能量暴走而毁灭整栋设施。

科研记录指出：

• 每个数字代表一段稳定能量，
• 加号表示能量的并行叠加，
• 一个合法的能量式必须是由若干合法能量式通过加法拼接而成。 换句话说，它是一个 若干正整数相加的表达式。

更糟糕的是，你不能随意造数字或加号，只能 任意重排 屏幕上的字符，且字符数量必须完全一致。

幸运的是，科学家已经证明： 给定的字符一定能重排成至少一个合法表达式。

你的任务是：将这串字符重新排列，使表达式的值尽可能小，并输出这个最小的值。

形式化的，给定一个只包含：数字字符 '1' 到 '9' 和加号字符 '+' 的字符串。你可以任意重新排列字符串中的所有字符，但必须保证每种字符的数量不变。

要求构造一个 合法的表达式*，使得表达式的值最小，并输出该最小值。

*合法表达式定义：

• 一个数字串（如 233）是一个合法表达式；
• A + B 是合法表达式，当且仅当 A 和 B 都是合法表达式。

保证一定存在至少一种排列方式，使得字符串表示一个合法表达式。

输入格式

一行输入一个字符串，仅包含数字1 - 9和加号+。

字符串s的长度在 $3 \leq len(s) \leq 5 \times 10^5$ 范围内，字符串的第一个和最后一个字符不为+号。

输出格式

一行输出一个数字，代表最小的解。

样例 1

111+1

22

样例 2

999876543211

112345678999

样例 3

12+35

38

提示

样例一说明：11+11=22 样例三说明：13+25=38