Maximum Subsequence

You are given a sequence of N integers, each of which is not greater than 10,000 considering absolute value. There are (N CK ) 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 44 1 2 3 4 41 1 2 3 4 42 4 4 -4 -4 00 Sample Output 10 4 8