Maximum Partition Product

You are given 40 (or more generally, at least 2) numbers. Your task is to partition these numbers into two non-empty groups. The weight of a group is defined as the sum of its elements. The weight of a partition is defined as the product of the two group weights.

More formally, if the two groups have sums \(x\) and \(S - x\) respectively where \(S\) is the sum of all the given numbers, the partition weight is \(x(S-x)\). You are required to compute the maximum possible partition weight.

Note: The input will consist of exactly one line containing the numbers separated by spaces (or newlines). There will be at least 2 numbers in the input.

inputFormat

The input consists of a single line (which may contain multiple spaces or newlines) with a list of integers. There will be at least 2 integers.

outputFormat

Output a single integer representing the maximum partition weight, i.e. the maximum value of \(x(S-x)\) where \(x\) is the sum of one partition and \(S\) is the total sum of all the numbers.

sample

5160 9191 6410 4657 7492 1531 8854 1253 4520 9231
1266 4801 3484 4323 5070 1789 2744 5959 9426 4433
4404 5291 2470 8533 7608 2935 8922 5273 8364 8819
7374 8077 5336 8495 5602 6553 3548 5267 9150 3309

12873625444