ケーブルをつなぐ
与えられた
n 本のケーブルの長さをすべてつなげて、1 本の長いケーブルを作りたいと考えます。長さが x と y の2 本のケーブルをつなぐ際には、x + y のコストがかかります。接続後、できあがったケーブルの長さは x + y となります。では、すべてのケーブルを1本にまとめるために支払う必要があるコストの最小値はいくらになるでしょうか？
入力
入力の最初の行には、ケーブルの本数を表す整数
n (1 ≤ n ≤ ) が与えられます。次の行には、ケーブルの長さを表す整数 (1 ≤ ≤ ) が空白区切りで与えられます。
出力
すべてのケーブルをつなげるのに必要なコストの最小値を出力してください。
サンプル
入力 | 出力 |
5
1 2 3 6 2 | 30 |
解説
- まず、長さ 1 と 2 のケーブルをつなぐ ⇒ コスト 3 ⇒ 結果: 3 3 6 2
- 次に、長さ 2 と 3 のケーブルをつなぐ ⇒ コスト 5 ⇒ 結果: 5 3 6
- 次に、長さ 3 と 5 のケーブルをつなぐ ⇒ コスト 8 ⇒ 結果: 6 8
- 最後に、長さ 6 と 8 のケーブルをつなぐ ⇒ コスト 14
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB