#P97. 接水问题

接水问题

题目描述

有N个人提着不同大小的水桶来接水,因为水桶大小不同,每个桶接满的时间也各不相同。

现在问你,给你每个人接水需要的时间,如何安排接水,让所有人等待的时间最少。

1<=N<=1000。

输入格式

第一行一个整数 N 后面有N行,每行一个整数Ai(1<=A<=100),第i个人接满水需要的时间,单位是秒。

输出格式

所有人把桶接满,等待时间的累加和。

样例

input

3
2
8
3

output

20  ( 先第一个人,再第三个,最后第二个)

限制与提示

时间限制:1s1 \text {s}

空间限制:256MB256 \text {MB}