문제 설명

동네 카페 '코드빈'에 오픈과 동시에 손님 N명이 한꺼번에 몰려 각자 음료를 주문했습니다. 바리스타는 한 번에 한 잔씩만 만들 수 있고, 각 주문의 조리시간(분)이 주어집니다. 손님은 자기 음료가 나올 때까지 기다리며, 한 손님의 '대기시간'은 주문이 끝나 음료를 받기까지 걸린 전체 시간입니다. 바리스타가 주문을 처리하는 순서를 자유롭게 정할 수 있을 때, 모든 손님의 대기시간 합이 최소가 되도록 순서를 정하고 그 최소 총 대기시간을 구하세요.

입력

출력

제약 조건

• •1 ≤ N ≤ 100,000
• •1 ≤ 각 조리시간 ≤ 1,000
• •바리스타는 동시에 한 잔만 만들 수 있다 (단일 처리)
• •모든 손님은 오픈 시각(0분)에 동시에 주문한다

예제

5
3 1 4 1 5

31

3
2 2 2

12