题目描述

搬家时要把 $n$ 件行李一件一件放进一个大箱子，第 $i$ 件行李重 $w_i$ 千克。

每放进去一件行李，都要把箱子放到秤上称一次，称重所需的时间等于当前箱子里所有行李的总重量（单位：秒）。

行李放入的顺序可以自己安排。求称完所有行李所需的最少总时间。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $w_i$。

输出格式

一行一个整数，表示最少总时间。

输入输出样例 #1

输入 #1

3
3 1 2

输出 #1

10

说明

数据范围

• 对于 $100\%$ 的数据，$1\le n\le 10^5$，$1\le w_i\le 10^9$。答案用 64 位整数存储不会溢出。

样例说明：按 $1,2,3$ 的顺序放，称重时间依次是 $1,3,6$，合计 $10$ 秒。