Going Back to the Definitions

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

One day, Gary woke up to realize that the foundations of mathematics had been completely restructured overnight.

It turns out that adding two numbers now means writing them side by side; that is, adding the R digit number A and the S digit number B is now defined as:

\displaystyle A_1A_2 \dots A_R + B_1B_2 \dots B_S = A_1A_2 \dots A_RB_1B_2 \dots B_S

For example, 123 + 45 = 12\,345, and 45 + 123 = 45\,123.

Mr. Ing draws N positive integers on the board, and he asks the class to determine the maximum possible sum of all N integers, provided they can be ordered in any way possible. Gary gets a little nervous when everyone else raises their hands almost instantly, and he needs your help to solve the question.

Input Specification

On the first line will be N (1 \le N \le 10\,000). On the next N lines, a single integer N_i (1 \le N_i \le 10^9) denoting one of the numbers Ing has written upon the board.

Output Specification

The maximum possible sum that can be obtained by adding the N numbers together in any order. Keep in mind that the output will be possibly extremely long and thus may not fit in a 128-bit integer.

Sample Input 1


Sample Output 1


Sample Input 2


Sample Output 2