Square from Digits with Largest Sum

You should write a program or function which receives a list of digits as input and outputs or returns the largest sum achievable by putting these digits in a square.

Input will always contain a square number of digits. An example square arrangement for the input 9 1 2 3 4 5 6 7 7 could be

677
943
125

The sum is calculated as the sum of all rows and columns. For the above arrangement the sum would be 677 + 943 + 125 + 691 + 742 + 735 = 3913. Note that this is not the maximal sum so this isn't the expected output.

Input

• A list with length n^2 (n>=1) containing non-zero digits (1-9).

Output

• An integer, the largest sum achievable with the input digits put in a square.

Examples

Example format is input => output.

5 => 10

1 2 3 4 => 137

5 8 6 8 => 324

9 1 2 3 4 5 6 7 7 => 4588

2 4 9 7 3 4 2 1 3 => 3823

8 2 9 4 8 1 9 3 4 6 3 8 1 5 7 1 => 68423

5 4 3 6 9 2 6 8 8 1 6 8 5 2 8 4 2 4 5 7 3 7 6 6 7 => 836445

This is code golf so the shortest entry wins.

• Just to double check, does the input have to be space-separated digits exactly or is an unambiguous list format okay? – Sp3000 Jul 21 '15 at 19:00
• @Sp3000 Any simple unambiguous list format is okay including the list format of your chosen language. – randomra Jul 21 '15 at 19:20

Pyth, 15 bytes

s*VSsM^^LTUQ2SQ

Note: Input in any python sequence format, such as a,b,c, or [a, b, c]. Fails on a.

This will be an explanation for the example input 5,8,6,8.

^LTUQ: This is a list of powers of 10, out to the length of Q. [1, 10, 100, 1000].

^ ... 2: Then, we take pairs of powers of 10. [[1, 1], [1, 10], ....

sM: Then, we sum those pairs. [2, 11, 101, ... Each number repesents the value of a grid location. The value of the bottom right corner is 2, because the digit placed there is in the ones place of the two numbers it is in. Note that 16 values were generated, even though we only need 4. This will be handled shortly.

S: Sort the value in increasing order. [2, 11, 11, 20, 101, .... Note that the only values which are relevant for this input are the first 4, because this square will not have hundreds or thousands places.

SQ: Sort the input in ascending order. [5, 6, 8, 8]

*V: Vectorized multiplication over the two lists. Pyth's vectorized multiplication truncates the longer input, so this performs [5*2, 6*11, 8*11, 8*20], equivalent to filling in the grid, smallest to largest, bottom right to top left.

s: Sum the results, 324. Printing is implicit.