Description

At university, there are many P.E. classes, and everyone can pick what they like. This semester, King chose basketball because the instructor is a very interesting person.

On the first day, the instructor announced the grading rules:

There are $n$ basketballs ($n \ge m$). The instructor has written an integer on each ball in advance (not necessarily distinct, with absolute value less than $10000$). There are $m$ baskets, and each basket has a counter displaying an integer. Before a student starts, all counters are initialized to $1$.

During the assessment, a student will take $n$ shots in total: for each shot, choose any basketball and throw it into any basket. In the end, all balls must be used and each ball must be used exactly once, and every basket must be used at least once.

If a ball labeled with integer $x$ is thrown into a basket whose counter currently displays $y$, then that basket’s counter changes from $y$ to $y \times x$.

A student’s raw score $S$ is defined as the sum of the $m$ counters’ displayed values. The larger $S$ is, the higher the final grade the instructor will assign (in fact, the instructor grades by ranking using a normal distribution, but that is beyond the scope of this problem).

King is a sharpshooter and guarantees every shot goes in. However, King is bad at math and does not know how to arrange the shots to maximize his raw score. Can you help him?

Input Format

Multiple testcases. Each testcase consists of two lines:

• The first line contains two integers $n, m$.
• The second line contains $n$ integers separated by spaces, which are the integers written on the $n$ basketballs.

The input ends with a line containing 0 0. There are at most $10$ testcases in a file.

Output Format

For each testcase, output one line containing an integer $S_{max}$, the maximum possible raw score.

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

Hint

• Constraints:

  • $1 \le m \le n \le 2000$.
  • Exactly $40\%$ of the testcases satisfy $n \le 100$.

• Notes:

  • $S_{max}$ may exceed any basic integer type.
  • $S_{max}$ may also be less than $0$.

• Sample Explanation:

  • The first testcase has multiple solutions; one solution is: $(0,0)(-1,-2,1,2,3,2,10,1)$.
  • The second testcase has multiple solutions; one solution is: $(0,0)(1,1)(-1,-2,2,3,2,10)$.

Translated by ChatGPT 5