In university, there are many physical education courses, and everyone can choose their favorite subject. King has chosen basketball this semester because the basketball teacher is a very interesting person.

On the first day of class, the teacher announced the grading rules for the course:

There are $n$ basketballs ($n \ge m$). The teacher has written an integer on each ball beforehand (not necessarily the same, with an absolute value less than $10000$). There are $m$ baskets, and each backboard has a scoreboard displaying an integer. Before a student begins the assessment, all scoreboards are initialized to $1$.

During the assessment, each student must perform $n$ shots: choose any basketball and shoot it into any basket. Finally, the student must have shot all the balls, with each ball being shot exactly once, and every basket must have been scored in at least once.

If a student shoots a basketball with an integer $x$ into a basket whose scoreboard displays $y$, the value on that backboard's scoreboard changes from $y$ to $y \times x$.

A student's raw score $S$ is defined as the sum of the values displayed on the $m$ scoreboards. The higher the $S$, the higher the final grade the teacher gives the student (in fact, the teacher grades based on rank according to a normal distribution, but this is beyond the scope of this problem).

King is a master shooter; he guarantees that he can make all $n$ shots. However, King is terrible at math, and he does not know how to arrange his shots to maximize his raw score. Can you help him?

Input

The input contains multiple test cases. Each test case consists of two lines: The first line contains two integers $n$ and $m$. The second line contains $n$ integers, separated by spaces, representing the integers written on the $n$ basketballs by the teacher. The file ends with $0\ 0$. There are at most $10$ test cases in a file.

Output

For each test case, output a single line containing an integer $S_{max}$, representing the maximum possible raw score.

Note: $S_{max}$ may exceed the range of any basic integer type. $S_{max}$ may also be less than $0$.

Constraints

• $1 \le m \le n \le 2000$
• Exactly $40\%$ of the data satisfies $n \le 100$

Examples

Input 1

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

Output 1

240
241

Note

The first test case has multiple solutions; one such solution is: $(0,0)(-1,-2,1,2,3,2,10,1)$ The second test case has multiple solutions; one such solution is: $(0,0)(1,1)(-1,-2,2,3,2,10)$