User's AC Ratio

88.5% (69/78)

Submission's AC Ratio

40.6% (82/202)

Description

  全國最大的便利商店正在舉行集點數換獎品的活動,任何參與者皆可以依據其收集到的貼紙點數,換得相對應的獎品。根據該活動的活動辦法,我們知道點數越高所能換得的獎品價值越高;但是,每次兌換獎品時,只限使用一張集點卡上所收集到的點數,不能合併多張集點卡的點數使用。
  小智目前手上共有$ n $張集點卡,為了換取最高價值的獎品,決定尋求科技公司的協助,將這些集點卡上的所有點數合併到單一集點卡上。然而,這家科技公司的服務有兩項規定:1) 一次只能合併兩張集點卡,2) 每次進行合併時,需收取和合併後點數相同數目的手續費。
  例如,若小智手上有$ 3 $張集點卡,上面的點數分別是$ 1, 3, 8$。若小智第一次合併點數為$ 1 $和$ 8 $的集點卡,則合併後的新集點卡點數為$ 9$,同時必須付$ 9 $元的手續費;接著,小智要合併點數為$ 3 $和$ 9 $的集點卡,合併後的點數為$ 12$,且手續費為$ 12 $元。因此,兩次合併的手續費總和為$ 9 + 12 = 21 $元。但是,若小智第一次合併點數為$ 1 $和$ 3 $的集點卡,則合併後的新集點卡點數為$ 4$,且手續費為 4 元;接著,小智合併點數為$ 4 $和$8 $的集點卡,合併後的點數為$ 12$,且手續費為$ 12 $元。因此,兩次合併的手續費總和為$ 4+ 12 = 16 $元。
  小智發現不同的合併順序,並不會影響最後合併完成時集點卡上的總點數,但卻會影響合併所需的手續費。請你幫忙小智計算合併$ n $張集點卡的最低手續費。

Input Format

輸入第一行有一個整數$n$,代表需要合併的集點卡張數;第二行有$n$個以空白符號相間隔的正整數,分別代表這$n$張集點卡原有收集到的點數。同時,輸入資料中,每一張集點卡上原有收集到的點數,皆為小於或等於$1000$的正整數。

Output Format

請根據輸入的資料,輸出合併這$n$張集點卡所需最低手續費。

Sample Input

#輸入範例1
3
1 3 8

#輸入範例2
4
8 3 5 1

Sample Output

#輸出範例1
16

#輸出範例2
30

Hints

Problem Source

臺北市105學年度高級中學資訊學科能力競賽程式設計試題第五題
Set by Yihda Yol

Subtasks

For Testdata: 0 ~ 11, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 524288 262144
1 1000 524288 262144
2 1000 524288 262144
3 1000 524288 262144
4 1000 524288 262144
5 1000 524288 262144
6 1000 524288 262144
7 1000 524288 262144
8 1000 524288 262144
9 1000 524288 262144
10 1000 524288 262144
11 1000 524288 262144