1194. 最小表达式

给出一个包含数字 1-9 和加号的字符串,请你将字符串中的字符任意排列,但每种字符数目不变,使得结果是一个合法的表达式,而且表达式的值最小。输出那个最小表达式的值。

合法的表达式的定义如下:

  • 一个数字,如 233,是一个合法的表达式

  • A + B 是合法的表达式,当且仅当 A , B 都是合法的表达式

保证给出的表达式经过重排,存在一个合法的解。

输入

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

字符串的长度小于等于 5 \cdot 10^5

输出

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

注意,答案长度可能长达 5 \cdot 10^5 个字符。

样例

标准输入 复制文本
111+1
标准输出 复制文本
22
标准输入 复制文本
9998765432111
标准输出 复制文本
1112345678999
标准输入 复制文本
12+35
标准输出 复制文本
38

提示

  • 11+11=22
  • 25+13 = 38

来源

2020 牛客寒假算法基础集训营

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 92
通过 21