Problem
Handsome Jack wants to set up his own Eridium processing plants.
There are n factories under Jack's control, each of them is numbered from 1 to n. Each plant is located at the Eridium deposit, where it is also mined in combination. And the higher the factory number, the newer it is.
Each plant has its efficiency index a
i. It can be positive, negative or zero.
Each plant must process Eridium ore. You can use your own deposit or take ore, processed in the past by another plant, through the pipeline. However, this process is somewhat limited. Firstly, in order not to overload the pipeline system, each plant can accept ore for further processing strictly from one another (or not accept and use its own deposit). Secondly, older plants are not technically capable of reprocessing ore after a newer plant.
The final performance of the entire system is calculated as follows: for each plant, its efficiency a
i is taken and multiplied by the processing stage, which is calculated as the number of the time the incoming ore is processed (for more details, see the explanations for the examples), then all the obtained values are summarized for all plants.
Help Handsome Jack organize the system so that the overall performance of the entire system is as high as possible.
Input:
The first line contains a natural number n (1 <= n <= 7) - the number of factories.
The second line contains n space-separated integers, where the i-th number is a
i (-1000 <= a
i <= 1000) - the base efficiency of the plant under number i.
Output:
Print a single number - the maximum possible total performance of the entire system.
Examples:
| Input |
Output |
3
1 5 3
| 20 |
3
1 5 -3 |
8 |
Explanations:
In the first example, it is most profitable for the first plant to mine its own ore, the second plant to receive ore from the first, and the third to receive from the second. In this case, the first plant performs primary processing and its productivity is 1 * 1 = 1. The second plant performs secondary processing, its productivity is 5 * 2 = 10. And the third plant processes the received ore for the third time, so its productivity is 3 * 3 = 9. Total performance is 1 + 10 + 9 = 20.
Please note that in this example, the second and third plants cannot be swapped, because the second plant will not be able to process ore after the third for technical reasons, because it is older than the third.
In the second example, the first and third factories will use their deposits, and the second factory will receive ore from the first.