You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

问题描述

有 n 堆石子，每堆石子的数量分别为 a1,a2,…,an 。每次可以将任意两堆石子合并成一堆，合并的代价是这两堆石子的数量之和。求将所有石子合并成一堆的最小总代价。

Format

Input

第一行：一个整数 n（1≤n≤$10^4$），表示石子的堆数。

第二行： n 个整数 a1,a2,…,an（1≤ai≤$10^4$)，表示每堆石子的数量。

Output

一个整数，表示最小总代价。

Samples

4
5 3 3 5

32

Limitation

1s, 1024KiB for each test case.