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.

题目描述

小Z购买了$n$个礼物，对于所有的$n$个礼物他都有自己的心意，其中第$i$个礼物代表着小Z的$a_{i}$的心意。现在，小Z有一个礼盒，每当他放进一个礼物后，礼盒表面的心意值都会增加当前礼盒内所有礼物的心意值之和。礼盒为空时，表面显示心意值为$0$。小Z想知道放完$n$个礼物后，礼盒能够显示的最大心意值。

输入格式

第一行输入一个整数$n$，代表礼物的总数量。

第二行输入$n$个整数，$a_{1},a_{2},a_{3},...,a_{n}$，其中$a_{i}$表示第$i$个礼物中小Z的心意值。（$1 \leq a_{i} \leq 10^5$）

输出格式

一个整数，表示礼盒能够显示的最大心意值。

输入输出样例 #1

输入 #1

5
1 5 2 4 2

输出 #1

52

输入输出样例 #2

输入 #2

8
2 1 3 1 3 1 5 1

输出 #2

99

说明/提示

对于全部测试点，保证$1 \leq n \leq 5000$。

注意礼物放进礼盒就不能再拿出来了。