[清北2012寒假]团队背包

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 tanbag.in 输出文件 tanbag.out

【题目描述】

DaA 和他的朋友组成一个团队去旅行了。他们每个人都准备了一个背包，用来装旅行用
的物品。他们的背包有两个特点：
1. 每个人的背包能装无限多的物品，每种物品有一个价值，但只能装一件；
2. 每个人都很有个性，所以每个人的背包不会完全相同。
DaA 的团队中有M 个人，那么对于整个团队，背包价值和最大是多少呢？

【输入格式】

第一行两个整数M、N，表示团队的人数和物品的数量。
接下来一行N 个整数，表示每件物品的价值wi。
数据保证不会出现有空背包人的出现。

【输出格式】

一个整数，整个团队背包价值的最大值。

【样例输入】 

Sample Input 1:
2 3
2 7 1
Sample Output 1:
19
Sample Input 2:
8 4
1 2 3 4
Sample Output 2:
58

【提示】

【样例解释】

19=(2+7+1)+(2+7)
58=(1+2+3+4)+(2+3+4)+(1+3+4)+(1+2+4)+(3+4)+(1+2+3)+(2+4)+(2+3)

【数据规模】
30%的数据 1<=M,N<=15。
60%的数据 1<=M<=200，1<=N<=100。
100%的数据 1<=M<=1,000,000，1<=N<=500，0<wi<=50。
输出请注意使用64 位整数（Pascal 中的Int64，C++中的long long）。

【来源】

清北学堂2012寒假培训 Test2