After the end of all the shooting competitions in XXIX Olympic Games in Beijing, Matthew Emmons will be known to more and more people because of his last - which is also his worst - shooting in the 50m Rifle 3*40 Men competitions. Four years before in Athens, he shot a wrong target and lost the gold metal which is almost at hands in the 50m Rifle 3*40 Men competition.

The following is Blue Mary's imagination :P

Emmons decides to practise shooting more assiduously. Because he is an excellent shooter, only 1 year later, he can even shoot precisely without collimation! To him, getting the gold metal of 50m Rifle 3*40 Men in XXX Olympic Games doesn't have any difficulty now.

His wife - Katerina Emmons, also a well-known excellent shooter - make a game to keep his interests with shot. The player has n (1<= n <=2000) bullets, each one has a value (a integer whose absolute value is less than 10000). There are m (1<= m <= n) targets, each with a point counter next to it. In the beginning of the game, all the counter are set to integer 1.

During the game, the player must choose a bullet and shoot any target. He must use all the bullet, each with at least(of course, at most) 1 time. And each target must be shot at least one time.

If the player shoot a target with a bullet valued X, the counter of the target will multiplied by X.

The final score of the game is sum of all the m counters.

Now Matthew needs your help to make his final score as high as possible. After that, he will show you his excellent shooting skills to get this score.

P.S. Even the things above is my imagination, I hope Matthew Emmons has good luck and wins the gold metal of 50m Rifle 3*40 Men in XXX Olympics in London.

Input

Multiple test cases, the number of them (<=50) is given in the very first line.

For each test case:

The first line contains two integers n and m. The second line contains n integers, the value for each bullet.

Output

For each test case:

The first and the only line contains a single integer - the highest possible final score.

Example

Input:
3
10 2
0 -1 -2 0 1 2 3 2 10 1
10 3
0 -1 -2 0 1 2 3 2 10 1
5 3
10 0 0 -1 -1
Output:
240
241
11
Hint:
For the first example, a possible solution is (0,0)(-1,-2,1,2,3,2,10,1).
For the second example, a possible solution is (0,0)(1,1)(-1,-2,2,3,2,10).