Merging Slimes

Interview

Time limit2sMemory limit512 MB

Summary

Merge N slimes two at a time, scoring the product of merged sizes, and maximize the total score.

Level: Medium4 of 10
Topics: Greedy, Sorting
Solved: No attempts yet

Problem

Yeongseon and Hyobin play a slime merging game. On each turn they pick two slimes and merge them into one. The game ends when a single slime is left.

Every slime has a positive size. Merging a slime of size $x$ with a slime of size $y$ produces one slime of size $x+y$ , and the two players score $x \times y$ points for that merge.

Write a program that finds the maximum total score Yeongseon and Hyobin can get.

Input

The first line contains the number of slimes $N$ ( $2 \le N \le 100$ ).

The second line contains the sizes of the $N$ slimes, separated by spaces. Each size is a natural number at most $100$ .

Output

Print the maximum total score Yeongseon and Hyobin can get on the first line.

Examples4

Example 1
Input
```
2
3 4
```
Expected output
```
12
```
Example 2
Input
```
3
2 2 2
```
Expected output
```
12
```
Example 3
Input
```
3
1 2 3
```
Expected output
```
11
```
Example 4
Input
```
3
3 1 2
```
Expected output
```
11
```