Page not loading? Try clicking here.
Placeholder

#8083
Subtask

Player-based Team Distribution 1s 1024MB

Problems

플레이어 N명이 1개 이상의 팀으로 나누어 게임을 진행하려 한다. 플레이어는 각각 정확히 한 팀에 속해야 한다. i번째 플레이어는 같은 팀에 속한 인원 수와 a_i를 곱한 것만큼의 점수를 얻는다.

팀을 적절히 나누었을 때, 모든 플레이어의 점수의 합의 최댓값을 구해보자.


Input

첫째 줄에 N (1 \leq N \leq 10^5)이 주어진다.

둘째 줄에 N개의 정수가 주어진다. i번째 수는 a_i이다. ( -10^5 \leq a_i \leq 10^5)


Output

첫째 줄에 팀을 적절히 나누었을 때 모든 플레이어들의 점수의 합의 최댓값을 출력한다.


Subtask

# Score Condition
#130

N \le 10

#210

A_i \le 0

#360

추가 제약 조건 없음


Example 

4
5 -9 3 7
36

하나의 팀에 5, 3, 7 를 갖는 선수가 속하고 다른 한 팀에 -9를 갖는 선수가 속한다.

이때 점수는 (5 + 3 + 7) * 3 - 9 = 45 - 9 = 36 이고 이보다 더 큰 값을 얻을 수 없다.



Source

2021 Sogang Programming Contest

You must sign in to write code.