背景

GESP六级真题(202506)

描述

班主任计划将班级⾥的 $n$ 名同学划分为若⼲个学习⼩组，每名同学都需要分⼊某⼀个学习⼩组中。观察发现，如果⼀个学习⼩组中恰好包含 $k$ 名同学，则该学习⼩组的讨论积极度为 $a_k$ 。

给定讨论积极度 $a_1, a_2, ..., a_n$ ，请你计算将这 $n$ 名同学划分为学习⼩组的所有可能⽅案中，讨论积极度之和的最⼤值。

格式

输入

第⼀⾏，⼀个正整数 $n$ ，表⽰班级⼈数。

第⼆⾏， $n$ 个⾮负整数 $a_1, a_2, ..., a_n$ ，表⽰不同⼈数学习⼩组的讨论积极度。

输出

输出共⼀⾏，⼀个整数，表⽰所有划分⽅案中，学习⼩组讨论积极度之和的最⼤值。

样例

4
1 5 6 3

10

8
0 2 5 6 4 3 3 4

12

数据规模

对于 40 % 的测试点，保证 $1 \le n \le 10$。

对于所有测试点，保证 $1 \le n \le 1000， 1 \le a_i \le 10^4$。

限制

时间限制：1.0 s

空间限制：512.0 MB