Problem Description
Damian is currently helping out as an orientation group leader. For the next activity, he has to divide the N participants under his care into groups of 3.
As we all know, everyone is crazy. Thus everyone has an associated craziness value Vi. When people are put together in a group, however, things become even worse - suffice to say, it multiplies like crazy!
The effective craziness of a group consisting of three people with craziness values of a, b and c is given by f(a, b, c) = a * b * c.
Not wanting to stress himself out more than necessary, Damian would like to form as many groups as possible, while minimising the sum of the effective craziness of the groups. People without a group do not contribute to this sum. Help him find this minimum sum.
Input
The first line contains one integer, N, the number of participants present.
The second line contains N space-separated integers, with the ith integer representing the craziness value of the ith participant.
Output
The output should contain one line containing one integer, the minimum sum of f(a, b, c) that can be achieved while still forming as many teams as possible.
Limits
For all subtasks, 0 ≤ Vi ≤ 106.
Subtask 1 (7%): 1 ≤ N ≤ 3.
Subtask 2 (19%): 1 ≤ N ≤ 11.
Subtask 3 (43%): 1 ≤ N ≤ 15.
Subtask 4 (18%): 1 ≤ N ≤ 17.
Subtask 5 (13%): 1 ≤ N ≤ 20.
Subtask 6 (0%): Sample Testcases.
Sample Testcase 1
Input
7
4 19 3 8 7 5 4
Output
232
Sample Output 1 Explanation
For the participants with craziness levels 3, 4, 4, 5, 7 and 8, the optimal way of grouping is (3, 5, 8) and (4, 4, 7) which gives a total of 3 * 5 * 8 + 4 * 4 * 7 = 232