You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给定一个正整数num，将num分割为两个非负整数，将分割的两个数拼接起来得到num各位数的任意一个排列，且出现的数字次数与num中数字出现次数保持一致（分离出的两个数可以包含前导0）。

请你编程计算出分割出来的两个数的和最小是多少？分割出来的两个数需要满足以下规律：

①为保证数字和的位数尽可能小，两个数字的位数要尽可能的接近。

②为保证两个数字各自尽可能小，两个数字的最高位要尽可能小，且保证最高位的情况下再使得次高位尽可能小……以此类推。

输入格式

从文件 digital.in 读入。

一行一个正整数num。

输出格式

输出到文件 digital.out。

输出分割后两个数的最小和。

样例输入输出

样例

94760

116

9811

37

样例解释

【样例1解释】 当94760分割为069和47时两个数的和最小，和为116。

【样例2解释】 将9811分割为18和19两个数，和最小，和为37。

数据范围

对于所有测试数据保证： $1 ≤ num ≤ 10^9$