[CTSC2006] 投篮游戏

题目描述

在大学里，体育课有很多门，每个人都可以选择自己最喜欢的项目。King 这学期选择了篮球，因为篮球课的老师是一个十分有趣的人。

上课的第一天，老师宣布了这门课的评分规则：

有 $n$ 个篮球（$n\ge m$），老师事先在每个球上写了一个整数。这些整数不一定相同，并且绝对值均小于 $10000$。

有 $m$ 个篮，每个篮板上都有一个计分器。考核开始前，所有计分器的显示值都被设为 $1$。

考核时，学生需要进行 $n$ 次投篮。每次选择一个尚未投出的篮球，并将它投向任意一个篮。最后必须满足：

• 每个篮球恰好被投出一次；
• 每个篮至少被投进过一次。

若一个写有整数 $x$ 的篮球被投进某个计分器当前显示为 $y$ 的篮，则该计分器的显示值变为

学生的原始得分 $S$ 定义为最后 $m$ 个计分器显示值之和。原始得分越高，最终成绩越好。

King 是一名神投手，能够保证所有篮球都投进目标篮筐。但他的数学很差，不知道怎样安排投篮才能使原始得分最大。请你求出最大可能的原始得分。

输入格式

输入包含多组测试数据。

每组测试数据包含两行：

• 第一行包含两个整数 $n,m$；
• 第二行包含 $n$ 个整数，表示每个篮球上写的数。

输入以一行 0 0 结束，该行不属于任何测试数据。

一个输入文件中最多包含 $10$ 组测试数据。

输出格式

对于每组测试数据，输出一行一个整数 $S_{\max}$，表示最大可能的原始得分。

答案可能超过任何基本整数类型的表示范围，也可能小于 $0$。

样例

10 2
0 -1 -2 0 1 2 3 2 10 1
10 3
0 -1 -2 0 1 2 3 2 10 1
0 0

240
241

数据范围

对于所有测试数据：

每个篮球上的整数绝对值小于 $10000$。

恰有 $40\%$ 的测试点满足 $n\le100$。

样例说明

第一组数据的一种最优分组为：

(0, 0) (-1, -2, 1, 2, 3, 2, 10, 1)

第二组数据的一种最优分组为：

(0, 0) (1, 1) (-1, -2, 2, 3, 2, 10)