Problem H
Maximum Subsequence

Input: Standard Input

Output: Standard Output

Time Limit: 2 Second

 

You are given a sequence of N integers, each of which is not greater than 10,000 considering absolute value. There are (NCK) sub-sequences possible from this sequence. You have to pick such a subsequence, so that multiplication of all its integers is maximum.

 

For example, if the sequence is 4, 4, -4, -4 and you are asked to pick 2 integers. You have 2 ways, which will satisfy the criterion. One is to pick 4,4 and the other is to pick –4, -4.

In this case, you have to consider the sub sequence whose summation of all integers is maximum.

 

Input

The input file contains several sets of inputs. The description of each set is given below.

 

Each input set starts with 2 positive integers N, K (1<=K<=N<=10000). Next N non-empty lines contain N integers in total.

 

Input is terminated by a case where N=0 and K=0. This case should not be processed. There will be at most 60 test cases.

 

Output

For each set of input print in a single line the summation of the integers in the desired subsequence.

 

Sample Input                               Output for Sample Input

4 4

1

2

3

4

4 1

1

2

3

4

4 2

4
4
–4
–4
0 0

10

4

8


Problem setter: Md. Kamruzzaman, EPS

Special Thanks: Monirul Hasan, EPS