TopCoder

User's AC Ratio

100.0% (38/38)

Submission's AC Ratio

59.1% (78/132)

Description

你剛剛解決了有人委託給你的「木材切割問題」,結果...

是的,身邊太多蘿莉也是會出事情的。
「我要3份喔膩醬!!」
「我要2份我要兩份!!」
「啊啊啊!!住手啊啊啊啊!」
---以下為自動屏蔽內容---

現在有N隻小蘿莉,每隻蘿莉想要ai份,令L= $ \sum_{i=1}^ {n}ai$,不妨假設你全身上下剛好可以等分成L單位吧,你要把這L單位拆成a1,a2,...,aN(不一定要按照順序)單位分送給各個蘿莉。
不過如果你將你一塊x單位的身體拆成兩塊你會恰好感到x單位的痛苦度,請問你至少會感到多少痛苦度以完成蘿莉的需求呢?
舉例來說,假設你身體分為10單位,而有4隻蘿莉分別想要2,2,3,3單位,考慮以下兩種切割方式。
第一種:
{10} 將10單位分成8,2。
{8,2} 將8單位分成6,2。
{6,2,2} 將6單位分成3,3。
{3,3,2,2} 完成,痛苦度為10+8+6=24。
第二種:
{10} 將10單位分成6,4。
{6,4} 將6單位分成3,3。
{4,3,3} 將4單位分成2,2。
{3,3,2,2} 完成,痛苦度為10+6+4=20。

而第二種也是所有切法裡最佳的。

Input Format

本題有多筆測資,請讀取到EOF結束。
對於每筆測資,
第一行有一個正整數N表示有N隻蘿莉。
第二行有N個以空格間隔的正整數ai依序表示第i隻蘿莉想要的單位數。

所有測資 : |ai|≤104

測資組A : N≤6
測資組B : N≤20
測資組C : N<51
測資組D : N≤1000
測資組E : N≤105

Output Format

對於每筆測資輸出一行,每行一個整數表示最小的痛苦度。

Sample Input

4
3 2 2 3
5
2 3 4 5 10
5
2 4 5 7 10

Sample Output

20
52
62

Hints

正當蘿莉拿起美工刀時,你醒了,發現只是一場夢而已。

Problem Source

Subtasks

For Testdata: 0 ~ 0, Score: 6
For Testdata: 1 ~ 1, Score: 20
For Testdata: 2 ~ 2, Score: 1
For Testdata: 3 ~ 3, Score: 46
For Testdata: 4 ~ 4, Score: 27
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536
1 1000 65536
2 1000 65536
3 1000 65536
4 1000 65536