{"trustable":true,"sections":[{"title":"Description","value":{"format":"MD","content":"In an orchard, DuoDuo has already picked all the fruits and divided them into different piles according to their types. DuoDuo decides to merge all the piles of fruits into one.\n\nEach time he merges, DuoDuo can merge two piles of fruits together, and the energy consumed is equal to the sum of the weights of the two piles of fruits. It can be seen that after $n-1$ merges, there is only one pile left. The total energy consumed by DuoDuo in merging the fruits is equal to the sum of the energy consumed for each merge.\n\nBecause it takes a lot of effort to carry these fruits back home, DuoDuo wants to save energy as much as possible when merging the fruits. Assuming each fruit weighs $1$, and the number of fruit types and the number of each type of fruit are known, your task is to design a merge order plan to minimize the energy consumption for DuoDuo, and output the minimum energy consumption value.\n\nFor example, there are $3$ types of fruits, with the numbers being $1$, $2$, $9$ respectively. You can first merge piles $1$ and $2$ together, resulting in a new pile with a number of $3$, and energy consumption of $3$. Then, merge the new pile with the third pile, resulting in a new pile with a number of $12$, and energy consumption of $12$. So, the total energy consumption for DuoDuo is $\u003d3+12\u003d15$. It can be proved that $15$ is the minimum energy consumption value."}},{"title":"Input","value":{"format":"MD","content":"Two lines in total. \nThe first line is an integer $n(1\\leq n\\leq 10000)$, representing the number of fruit types. \nThe second line contains $n$ integers separated by spaces, where the $i$-th integer $a_i(1\\leq a_i\\leq 20000)$ represents the number of the $i$-th type of fruit."}},{"title":"Output","value":{"format":"MD","content":"An integer, which is the minimum energy consumption value. It is guaranteed that this value is less than $2^{31}$."}},{"title":"Sample 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 \n1 2 9 \n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Hint","value":{"format":"MD","content":"For data of $30\\%$, it is guaranteed that there is $n \\le 1000$: \nFor data of $50\\%$, it is guaranteed that there is $n \\le 5000$; \nFor all data, it is guaranteed that there is $n \\le 10000$."}}]}