Adding Numbers

Interview

Time limit1sMemory limit128 MB

Summary

Split the given digits into two numbers with no leading zero so their sum is as small as possible.

Level: Medium5 of 10
Topics: Brute force, Sorting, Greedy
Solved: No attempts yet

Problem

When Gangmin was in third grade, his homeroom teacher gave the class this problem.

Use each of the digits 1, 2, 7, 8, 9 exactly once to build two numbers, then add them. What is the smallest sum you can get?

Gangmin decided the answer was 207 (78 + 129). The teacher then assigned every similar problem on page 4 of the book as homework.

Gangmin had started programming the year before, and coding was more fun to him than homework, so he decided to finish the assignment with a program.

Use every given digit exactly once and split the digits into two numbers. Each number takes at least one digit and cannot start with 0. Build the two numbers so that their sum is as small as possible, and print that sum.

Input

The input has several lines, and each line holds one practice problem.

The first integer on a line, $N$ ( $2 \le N \le 14$ ), is how many digits that practice problem uses. The $N$ digits follow, separated by spaces, and each digit is between 0 and 9. At least two of them are not 0.

A line whose first integer is 0 ends the input.

Output

For each practice problem, print the smallest sum of the two numbers on its own line.

Examples1

Example 1

Input

5 1 2 7 8 9
6 3 4 2 2 2 2
9 0 1 2 3 4 0 1 2 3
0

Expected output

207
447
11257