鈴木さんは会津地域に新しく搾りたてミルクの移動販売のお店を開きました。その日買い求めに来るお客さんは全員持ち帰るためのボトルを持って既にお店に並んでいて、それ以上増えないものとします。お客さんはそれぞれ1回だけしか注文しません。タンクの蛇口が一つしかないので、一人ずつ順番に販売しなければなりません。そこで、鈴木さんはなるべく並んでいるお客さんの待ち時間を少なくしたいと考えています。
お客さんの人数とお客さんが牛乳を注ぎきるのに要する時間が入力として与えられます。あなたはお客さんの「一人一人の待ち時間の合計」(以下「待ち時間の合計」とする)を最小にするための注文の順序を鈴木さんに代わって調べ、そのときの「待ち時間の合計」を出力して終了するプログラムを作成してください。ただし、お客さんは 10,000 人以下で 1 人あたりに要する時間は 60 分以下とします。
例えば、お客さんの人数が 5 人で、各お客さんが要する時間が順に 2,6,4,3,9 分の場合、そのままの順序だと「待ち時間の合計」は 37 分になります。次の例では、最初の列の順の 2 人目と 3 人目を入れ替えています。この場合、「待ち時間の合計」は 35 分になります。最適な順序だと 31 分で済みます。
| 待ち時間 | ||
| 1 人目 2 分 | 0 分 | |
| 2 人目 6 分 | 2 分 | |
| 3 人目 4 分 | 8 分 | |
| 4 人目 3 分 | 12 分 | |
| 5 人目 9 分 | 15 分 | |
| 37 分 | ← 「待ち時間の合計」 |
2 人目と 3 人目を入れ替えた例
| 待ち時間 | ||
| 1 人目 2 分 | 0 分 | |
| 2 人目 4 分 | 2 分 | |
| 3 人目 6 分 | 6 分 | |
| 4 人目 3 分 | 12 分 | |
| 5 人目 9 分 | 15 分 | |
| 35 分 | ← 「待ち時間の合計」 |
複数のデータセットが与えられます。各データセットは以下の形式で与えられます。
n t1 t2 : tn
1 行目にお客さんの人数 n (n ≤ 10,000) が与えられます。続く n 行に i 人目のお客さんが要する時間を表す整数 ti (0 ≤ ti ≤ 60) がそれぞれ１行に与えられます。
入力は１つの 0 を含む行で終わります。データセットの数は 50 を超えません。
各データセットごとに、待ち時間の合計(整数)を１行に出力してください。
5 2 6 4 3 9 0
31