Bé Tý có \(N\) que gỗ, que thứ \(i\) có độ dài \(a_i\). Tý muốn gộp chúng thành một que duy nhất. Mỗi lần gộp, Tý chọn hai que bất kỳ và nối chúng lại, chi phí bằng tổng độ dài hai que đó.

Hãy giúp Tý tìm tổng chi phí nhỏ nhất để gộp tất cả các que.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên \(N\) (\(2 \le N \le 10^5\)).
• Dòng thứ hai chứa \(N\) số nguyên \(a_1, a_2, ..., a_N\) (\(1 \le a_i \le 10^9\)).

Kết quả ra

• In ra tổng chi phí nhỏ nhất (kết quả có thể vượt quá 32-bit).

Ví dụ

Input

4
4 3 2 6

Output

29